Some Variations of Perfect Graphs
Magda Dettlaff; Magdalena Lemańska; Gabriel Semanišin; Rita Zuazua
Discussiones Mathematicae Graph Theory (2016)
- Volume: 36, Issue: 3, page 661-668
- ISSN: 2083-5892
Access Full Article
top
Abstract
topHow to cite
topMagda Dettlaff, et al. "Some Variations of Perfect Graphs." Discussiones Mathematicae Graph Theory 36.3 (2016): 661-668. <http://eudml.org/doc/285594>.
@article{MagdaDettlaff2016,
abstract = {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.},
author = {Magda Dettlaff, Magdalena Lemańska, Gabriel Semanišin, Rita Zuazua},
journal = {Discussiones Mathematicae Graph Theory},
keywords = {k-path vertex cover; distance k-domination number; perfect graphs; -path vertex cover; distance -domination number},
language = {eng},
number = {3},
pages = {661-668},
title = {Some Variations of Perfect Graphs},
url = {http://eudml.org/doc/285594},
volume = {36},
year = {2016},
}
TY - JOUR
AU - Magda Dettlaff
AU - Magdalena Lemańska
AU - Gabriel Semanišin
AU - Rita Zuazua
TI - Some Variations of Perfect Graphs
JO - Discussiones Mathematicae Graph Theory
PY - 2016
VL - 36
IS - 3
SP - 661
EP - 668
AB - 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.
LA - eng
KW - k-path vertex cover; distance k-domination number; perfect graphs; -path vertex cover; distance -domination number
UR - http://eudml.org/doc/285594
ER -
References
top- [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] Zbl1223.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] Zbl1078.05064
- [5] T. Haynes, S. Hedetniemi and P. Slater, Fundamentals of Domination in Graphs (Marcel Dekker, 1998). Zbl0890.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. Zbl0766.05040
- [7] M.A. Henning, O.R. Oellermann and H.C. Swart, Relationships between distance domination parameters, Math. Pannon. 5 (1994) 69-79. Zbl0801.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] Zbl1037.05038
NotesEmbed ?
topYou must be logged in to post comments.
To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.