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.
@article{bwmeta1.element.doi-10_7151_dmgt_1880,
author = {Magda Dettlaff and Magdalena Lema\'nska and Gabriel Semani\v sin and Rita Zuazua},
title = {Some Variations of Perfect Graphs},
journal = {Discussiones Mathematicae Graph Theory},
volume = {36},
year = {2016},
pages = {661-668},
zbl = {1339.05154},
language = {en},
url = {http://dml.mathdoc.fr/item/bwmeta1.element.doi-10_7151_dmgt_1880}
}
Magda Dettlaff; Magdalena Lemańska; Gabriel Semanišin; Rita Zuazua. Some Variations of Perfect Graphs. Discussiones Mathematicae Graph Theory, Tome 36 (2016) pp. 661-668. http://gdmltest.u-ga.fr/item/bwmeta1.element.doi-10_7151_dmgt_1880/
[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] | Zbl 1223.05224
[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] | Zbl 1078.05064
[5] T. Haynes, S. Hedetniemi and P. Slater, Fundamentals of Domination in Graphs (Marcel Dekker, 1998). | Zbl 0890.05002
[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. | Zbl 0766.05040
[7] M.A. Henning, O.R. Oellermann and H.C. Swart, Relationships between distance domination parameters, Math. Pannon. 5 (1994) 69-79. | Zbl 0801.05038
[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] | Zbl 1037.05038