# Graphs without induced P₅ and C₅

Discussiones Mathematicae Graph Theory (2004)

- Volume: 24, Issue: 3, page 503-507
- ISSN: 2083-5892

## Access Full Article

top## Abstract

top## How to cite

topGabor Bacsó, and Zsolt Tuza. "Graphs without induced P₅ and C₅." Discussiones Mathematicae Graph Theory 24.3 (2004): 503-507. <http://eudml.org/doc/270534>.

@article{GaborBacsó2004,

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.},

author = {Gabor Bacsó, Zsolt Tuza},

journal = {Discussiones Mathematicae Graph Theory},

keywords = {graph domination; connected domination; complete subgraph; forbidden induced subgraph; characterization},

language = {eng},

number = {3},

pages = {503-507},

title = {Graphs without induced P₅ and C₅},

url = {http://eudml.org/doc/270534},

volume = {24},

year = {2004},

}

TY - JOUR

AU - Gabor Bacsó

AU - Zsolt Tuza

TI - Graphs without induced P₅ and C₅

JO - Discussiones Mathematicae Graph Theory

PY - 2004

VL - 24

IS - 3

SP - 503

EP - 507

AB - 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.

LA - eng

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

UR - http://eudml.org/doc/270534

ER -

## References

top- [1] G. Bacsó and Zs. Tuza, Dominating cliques in P₅-free graphs, Periodica Math. Hungar. 21 (1990) 303-308, doi: 10.1007/BF02352694. Zbl0746.05065
- [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. Zbl0698.05039
- [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. Zbl0729.05043
- [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. Zbl1037.05038

## NotesEmbed ?

topTo embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.