Graphs without induced P₅ and C₅

Gabor Bacsó; Zsolt Tuza

Discussiones Mathematicae Graph Theory (2004)

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

Abstract

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

How to cite

top

Gabor 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. [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. [2] G. Bacsó and Zs. Tuza, Structural domination of graphs, Ars Combinatoria 63 (2002) 235-256. 
  3. [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. [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. [5] W. Goddard and M.A. Henning, Total domination perfect graphs, to appear in Bull. ICA. 
  6. [6] I.E. Zverovich, Perfect connected-dominant graphs, Discuss. Math. Graph Theory 23 (2003) 159-162, doi: 10.7151/dmgt.1192. Zbl1037.05038

NotesEmbed ?

top

You must be logged in to post comments.

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

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.