Discussiones Mathematicae Graph Theory 24(3) (2004) 503-507

GRAPHS WITHOUT INDUCED P_5 AND C_5

Gabor Bacsó and Zsolt Tuza

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 P5 and C5. Here we show (with an independent proof) that the following stronger result is also valid: Every P5-free and C5-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.

2000 Mathematics Subject Classification: 05C69.

References

[1] G. Bacsó and Zs. Tuza, Dominating cliques in P5-free graphs, Periodica Math. Hungar. 21 (1990) 303-308, doi: 10.1007/BF02352694.
[2] G. Bacsó and Zs. Tuza, Structural domination of graphs, Ars Combinatoria 63 (2002) 235-256.
[3] F.R.K. Chung, A. Gyárfás, W.T. Trotter and Zs. Tuza, The maximum number of edges in 2K2-free graphs of bounded degree, Discrete Math. 81 (1990) 129-135, doi: 10.1016/0012-365X(90)90144-7.
[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.
[5] W. Goddard and M.A. Henning, Total domination perfect graphs, to appear in Bull. ICA.
[6] I.E. Zverovich, Perfect connected-dominant graphs, Discuss. Math. Graph Theory 23 (2003) 159-162, doi: 10.7151/dmgt.1192.

Received 21 July 2003
Revised 5 February 2004