Domination in graphs of minimum degree at least two and large girth

Löwenstein, Christian; Rautenbach, Dieter GND

We prove that for graphs of order n, minimum degree 2 and girth g 5 the domination number satisfies 1 3 + 2 3gn. As a corollary this implies that for cubic graphs of order n and girth g 5 the domination number satisfies 44 135 + 82 135gn which improves recent results due to Kostochka and Stodolsky (An upper bound on the domination number of n-vertex connected cubic graphs, manuscript (2005)) and Kawarabayashi, Plummer and Saito (Domination in a graph with a 2-factor, J. Graph Theory 52 (2006), 1-6) for large enough girth. Furthermore, it confirms a conjecture due to Reed about connected cubic graphs (Paths, stars and the number three, Combin. Prob. Comput. 5 (1996), 267-276) for girth at least 83.

Cite

Citation style:
Löwenstein, C., Rautenbach Prof. Dr. rer. nat. habil., D., 2007. Domination in graphs of minimum degree at least two and large girth. Preprint /  Technische Universität Ilmenau, Institut für Mathematik, Preprint /  Technische Universität Ilmenau, Institut für Mathematik 07–09.
Could not load citation form. Default citation form is displayed.

Rights

Use and reproduction:
All rights reserved

Export