Geodesic
Some Variations of Perfect Graphs
Discussiones Mathematicae. Graph Theory, Tome 36 (2016) no. 3, pp. 661-668 Cet article a éte moissonné depuis la source Library of Science

Voir la notice de l'article

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.
Keywords: k-path vertex cover, distance k-domination number, perfect graphs 
@article{DMGT_2016_36_3_a10,
     author = {Dettlaff, Magda and Lema\'nska, Magdalena and Semani\v{s}in, Gabriel and Zuazua, Rita},
     title = {Some {Variations} of {Perfect} {Graphs}},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {661--668},
     year = {2016},
     volume = {36},
     number = {3},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2016_36_3_a10/}
}
TY  - JOUR
AU  - Dettlaff, Magda
AU  - Lemańska, Magdalena
AU  - Semanišin, Gabriel
AU  - Zuazua, Rita
TI  - Some Variations of Perfect Graphs
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2016
SP  - 661
EP  - 668
VL  - 36
IS  - 3
UR  - http://geodesic.mathdoc.fr/item/DMGT_2016_36_3_a10/
LA  - en
ID  - DMGT_2016_36_3_a10
ER  - 
%0 Journal Article
%A Dettlaff, Magda
%A Lemańska, Magdalena
%A Semanišin, Gabriel
%A Zuazua, Rita
%T Some Variations of Perfect Graphs
%J Discussiones Mathematicae. Graph Theory
%D 2016
%P 661-668
%V 36
%N 3
%U http://geodesic.mathdoc.fr/item/DMGT_2016_36_3_a10/
%G en
%F DMGT_2016_36_3_a10
Dettlaff, Magda; Lemańska, Magdalena; Semanišin, Gabriel; Zuazua, Rita. Some Variations of Perfect Graphs. Discussiones Mathematicae. Graph Theory, Tome 36 (2016) no. 3, pp. 661-668. http://geodesic.mathdoc.fr/item/DMGT_2016_36_3_a10/

[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

[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

[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

[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

[9] I.E. Zverovich, Perfect-connected-dominant graphs, Discuss. Math. Graph Theory 23 (2003) 159-162. doi:10.7151/dmgt.1192