Some Variations of Perfect Graphs

• Autorzy: Magda Dettlaff , Magdalena Lemańska , Gabriel Semanišin , Rita Zuazua
• 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.

Słowa kluczowe

EN

k-path vertex cover; distance k-domination number; perfect graphs

• Wydawca: De Gruyter Open
• Czasopismo: Discussiones Mathematicae Graph Theory
• Rocznik: 2016
• Tom: 36
• Numer: 3
• Strony: 661-668

Daty

wydano

2016-08-01

otrzymano

2015-03-03

poprawiono

2015-09-23

zaakceptowano

2015-10-09

online

2016-07-06

Twórcy

autor

Magda Dettlaff

• Faculty of Applied Physics and Mathematics Gdańsk University of Technology ul. Narutowicza 11/12, 80–233 Gdańsk, Poland

autor

Magdalena Lemańska

• Faculty of Applied Physics and Mathematics Gdańsk University of Technology ul. Narutowicza 11/12, 80–233 Gdańsk, Poland

autor

Gabriel Semanišin

• Institute of Computer Science P.J. Šafárik University Jesenná 5, 041 54 Košice, Slovakia

autor

Rita Zuazua

• Faculty of Science National Autonomous University of Mexico Av. Universidad 3000, Mexico City, Mexico

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]

Identyfikatory

DOI

10.7151/dmgt.1880