Search
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.
Citations
-
1
CrossRef
-
0
Web of Science
-
2
Scopus
Authors (4)
-
Gabriel Semanišin
- P.J. Safarik University Institute of Computer Science
-
Rita Zuazua
- National Autonomous University of Mexico Faculty of Science
Cite as
Full text
download paper
downloaded 22 times
- Publication version
- Accepted or Published Version
- DOI:
- Digital Object Identifier (open in new tab) 10.7151/dmgt.1880
- License
-
open in new tab
Keywords
Details
- Category:
- Articles
- Type:
- artykuł w czasopiśmie wyróżnionym w JCR
- Published in:
-
Discussiones Mathematicae Graph Theory
no. 36,
edition 3,
pages 661 - 668,
ISSN: 1234-3099 - Language:
- English
- Publication year:
- 2016
- Bibliographic description:
- Dettlaff M., Lemańska M., Semanišin G., Zuazua R.: Some variations of perfect graphs// Discussiones Mathematicae Graph Theory. -Vol. 36, iss. 3 (2016), s.661-668
- DOI:
- Digital Object Identifier (open in new tab) 10.7151/dmgt.1880
- Verified by:
- Gdańsk University of Technology
seen 131 times
Recommended for you
Total domination in versus paired-domination in regular graphs
- J. Cyman,
- M. Dettlaff,
- M. A. Henning
- + 2 authors
2018
On extremal sizes of locally k-tree graphs
- M. Borowiecki,
- P. Borowiecki,
- E. Sidorowicz
- + 1 authors
2010
Minimum order of graphs with given coloring parameters
- G. Bacsó,
- P. Borowiecki,
- M. Hujter
- + 1 authors
2015