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.
@article{bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1248,
author = {Gabor Bacs\'o and Zsolt Tuza},
title = {Graphs without induced P5 and C5},
journal = {Discussiones Mathematicae Graph Theory},
volume = {24},
year = {2004},
pages = {503-507},
zbl = {1064.05108},
language = {en},
url = {http://dml.mathdoc.fr/item/bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1248}
}
Gabor Bacsó; Zsolt Tuza. Graphs without induced P₅ and C₅. Discussiones Mathematicae Graph Theory, Tome 24 (2004) pp. 503-507. http://gdmltest.u-ga.fr/item/bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1248/
[000] [1] G. Bacsó and Zs. Tuza, Dominating cliques in P₅-free graphs, Periodica Math. Hungar. 21 (1990) 303-308, doi: 10.1007/BF02352694. | Zbl 0746.05065
[001] [2] G. Bacsó and Zs. Tuza, Structural domination of graphs, Ars Combinatoria 63 (2002) 235-256.
[002] [3] 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. | Zbl 0698.05039
[003] [4] 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. | Zbl 0729.05043
[004] [5] W. Goddard and M.A. Henning, Total domination perfect graphs, to appear in Bull. ICA.
[005] [6] I.E. Zverovich, Perfect connected-dominant graphs, Discuss. Math. Graph Theory 23 (2003) 159-162, doi: 10.7151/dmgt.1192. | Zbl 1037.05038