Czasopismo
Tytuł artykułu
Warianty tytułu
Języki publikacji
Abstrakty
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.
Słowa kluczowe
Wydawca
Czasopismo
Rocznik
Tom
Numer
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
autor
- Faculty of Applied Physics and Mathematics Gdańsk University of Technology ul. Narutowicza 11/12, 80–233 Gdańsk, Poland, magda@pg.gda.pl
autor
- Faculty of Applied Physics and Mathematics Gdańsk University of Technology ul. Narutowicza 11/12, 80–233 Gdańsk, Poland
autor
- Institute of Computer Science P.J. Šafárik University Jesenná 5, 041 54 Košice, Slovakia, gabriel.semanisin@upjs.sk
autor
- Faculty of Science National Autonomous University of Mexico Av. Universidad 3000, Mexico City, Mexico, ritazuazua@ciencias.unam.mx
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