PL EN


Preferencje help
Widoczny [Schowaj] Abstrakt
Liczba wyników
2016 | 36 | 3 | 661-668
Tytuł artykułu

Some Variations of Perfect Graphs

Treść / Zawartość
Warianty tytułu
Języki publikacji
EN
Abstrakty
EN
We consider (ψk−γk−1)-perfect graphs, i.e., graphs G for which ψk(H) = γk−1(H) for any induced subgraph H of G, where ψk and γk−1 are the k-path vertex cover number and the distance (k − 1)-domination number, respectively. We study (ψk−γk−1)-perfect paths, cycles and complete graphs for k ≥ 2. Moreover, we provide a complete characterisation of (ψ2 − γ1)- perfect graphs describing the set of its forbidden induced subgraphs and providing the explicit characterisation of the structure of graphs belonging to this family.
Wydawca
Rocznik
Tom
36
Numer
3
Strony
661-668
Opis fizyczny
Daty
wydano
2016-08-01
otrzymano
2015-03-03
poprawiono
2015-09-23
zaakceptowano
2015-10-09
online
2016-07-06
Twórcy
  • Faculty of Applied Physics and Mathematics Gdańsk University of Technology ul. Narutowicza 11/12, 80–233 Gdańsk, Poland, magda@pg.gda.pl
  • Faculty of Applied Physics and Mathematics Gdańsk University of Technology ul. Narutowicza 11/12, 80–233 Gdańsk, Poland
autor
Bibliografia
  • [1] C. Berge, Färbung von Graphen, deren samtliche bzw. deren ungerade Kreise starr sind, Wiss. Z. Martin-Luther-Univ. Halle-Wittenberg Math.-Natur. Reihe 10 (1961) 114.
  • [2] A. Brandstädt, V.B. Le and J.P. Spinrad, Graph Classes: A Survey (Monographs on Discrete Math. Appl.) (SIAM, Philadelphia, 1999). doi:10.1137/1.9780898719796[Crossref]
  • [3] B. Brešar, F. Kardoš, J. Katrenič and G. Semanišin, Minimum k-path vertex cover , Discrete Appl. Math. 159 (2011) 1189-1195. doi:10.1016/j.dam.2011.04.008[Crossref][WoS]
  • [4] G.S. Domke, J.H. Hattingh and L.R. Markus, On weakly connected domination in graphs II, Discrete Math. 305 (2005) 112-122. doi:10.1016/j.disc.2005.10.006[Crossref]
  • [5] T. Haynes, S. Hedetniemi and P. Slater, Fundamentals of Domination in Graphs (Marcel Dekker, 1998).
  • [6] M.A. Henning, O.R. Oellermann and H.C. Swart, Bounds on distance domination parameters, J. Combin. Inform. System Sci. 16 (1991) 11-18.
  • [7] M.A. Henning, O.R. Oellermann and H.C. Swart, Relationships between distance domination parameters, Math. Pannon. 5 (1994) 69-79.
  • [8] L. Volkmann, On graphs with equal domination and covering numbers, Discrete Appl. Math. 51 (1994) 211-217. doi:10.1016/0166-218X(94)90110-4[Crossref]
  • [9] I.E. Zverovich, Perfect-connected-dominant graphs, Discuss. Math. Graph Theory 23 (2003) 159-162. doi:10.7151/dmgt.1192[Crossref]
Typ dokumentu
Bibliografia
Identyfikatory
Identyfikator YADDA
bwmeta1.element.doi-10_7151_dmgt_1880
JavaScript jest wyłączony w Twojej przeglądarce internetowej. Włącz go, a następnie odśwież stronę, aby móc w pełni z niej korzystać.