Graphs without induced P₅ and C₅

• Autorzy: Gabor Bacsó , Zsolt Tuza
• Języki publikacji: EN

Abstrakty

EN

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.

Słowa kluczowe

EN

graph domination; connected domination; complete subgraph; forbidden induced subgraph; characterization

Kategorie tematyczne

• 05C69: Dominating sets, independent sets, cliques

• Wydawca: De Gruyter Open
• Czasopismo: Discussiones Mathematicae Graph Theory
• Rocznik: 2004
• Tom: 24
• Numer: 3
• Strony: 503-507

Daty

wydano

2004

otrzymano

2003-07-21

poprawiono

2004-02-05

Twórcy

autor

Gabor Bacsó

• Computer and Automation Institute, Hungarian Academy of Sciences, 1111 Budapest, Kende u. 13-17, Hungary

autor

Zsolt Tuza

• Computer and Automation Institute, Hungarian Academy of Sciences, 1111 Budapest, Kende u. 13-17, Hungary

Bibliografia

• [1] G. Bacsó and Zs. Tuza, Dominating cliques in P₅-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 2K₂-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.

Identyfikatory

DOI

10.7151/dmgt.1248