ArticleOriginal scientific text
Title
Graphs without induced P₅ and C₅
Authors 1, 1
Affiliations
- Computer and Automation Institute, Hungarian Academy of Sciences, 1111 Budapest, Kende u. 13-17, Hungary
Abstract
Zverovich [Discuss. Math. Graph Theory 23 (2003), 159-162.] has proved that the domination number and connected domination number are equal on all connected graphs without induced P₅ and C₅. Here we show (with an independent proof) that the following stronger result is also valid: Every P₅-free and C₅-free connected graph contains a minimum-size dominating set that induces a complete subgraph.
Keywords
graph domination, connected domination, complete subgraph, forbidden induced subgraph, characterization
Bibliography
- G. Bacsó and Zs. Tuza, Dominating cliques in P₅-free graphs, Periodica Math. Hungar. 21 (1990) 303-308, doi: 10.1007/BF02352694.
- G. Bacsó and Zs. Tuza, Structural domination of graphs, Ars Combinatoria 63 (2002) 235-256.
- F.R.K. Chung, A. Gyárfás, W.T. Trotter and Zs. Tuza, The maximum number of edges in 2K₂-free graphs of bounded degree, Discrete Math. 81 (1990) 129-135, doi: 10.1016/0012-365X(90)90144-7.
- M.B. Cozzens and L.L. Kelleher, Dominating cliques in graphs, Discrete Math. 86 (1990) 101-116, doi: 10.1016/0012-365X(90)90353-J.
- W. Goddard and M.A. Henning, Total domination perfect graphs, to appear in Bull. ICA.
- I.E. Zverovich, Perfect connected-dominant graphs, Discuss. Math. Graph Theory 23 (2003) 159-162, doi: 10.7151/dmgt.1192.
Pages:
503-507
Main language of publication
English
Received
2003-07-21
Accepted
2004-02-05
Published
2004
DOI: 10.7151/dmgt.1248
Exact and natural sciences