Abstract
We prove that for graphs of order n, minimum degree δ ≥ 2 and girth g ≥ 5 the domination number γ satisfies \(\gamma\leq\left(\frac{1}{3}+\frac{2}{3g}\right)n\). As a corollary this implies that for cubic graphs of order n and girth g ≥ 5 the domination number γ satisfies \(\gamma \leq \left(\frac{44}{135}+\frac{82}{135g}\right)n\) 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.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Blank, M.: An estimate of the external stability number of a graph without suspended vertices. Prikl Math i Programmirovanie Vyp 10, 3–11 (1973)
Brigham, R.C., Dutton, R.D.: Bounds on the domination number of a graph. Q. J. Math., Oxf. II. Ser. 41, 269–275 (1990)
Brooks, R.L.: On colouring the nodes of a network. Proc. Cambridge Philos. Soc. 37, 194–197 (1941)
Haynes, T.W., Hedetniemi, S.T., Slater, P.J.: Fundamentals of domination in graphs. Marcel Dekker, Inc., New York (1998)
Haynes, T.W., Hedetniemi, S.T., Slater, P.J.: Domination in graphs advanced topics. Marcel Dekker, Inc., New York (1998)
Kawarabayashi, K., Plummer, M.D., Saito, A.: Domination in a graph with a 2-factor. J. Graph Theory 52, 1–6 (2006)
Kostochka, A.V., Stodolsky, B.Y.: On domination in connected cubic graphs. Discrete Math. 304, 45–50 (2005)
Kostochka, A.V., Stodolsky, B.Y.: An upper bound on the domination number of n-vertex connected cubic graphs. manuscript (2005)
McCuaig, W., Shepherd, B.: Domination in graphs with minimum degree two. J. Graph Theory 13, 749–762 (1989)
Ore, O.: Theory of graphs. Amer. Math. Soc. Colloq. Publ. 38 (1962)
Randerath, B., Volkmann, L.: Characterization of graphs with equal domination and covering number. Discrete Math. 191, 159–169 (1998)
Rautenbach, D.: A Note on domination, girth and minimum degree. Discrete Math. (to appear)
Reed, B.: Paths, stars and the number three. Combin. Prob. Comput. 5, 267–276 (1996)
Volkmann, L.: Upper bounds on the domination number of a graph in terms of diameter and girth. J. Combin. Math. Combin. Comput. 52, 131–141 (2005)
Volkmann, L.: An upper bound for the domination number of a graph in terms of order and girth. J. Combin. Math. Combin. Comput. 54, 195–212 (2005)
Xu, B., Cockayne, E.J., Haynes, T.H., Hedetniemi, S.T., Zhou, S.: Extremal graphs for inequalities involving domination parameters. Discrete Math. 216, 1–10 (2000)
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Löwenstein, C., Rautenbach, D. Domination in Graphs of Minimum Degree at least Two and Large Girth. Graphs and Combinatorics 24, 37–46 (2008). https://doi.org/10.1007/s00373-007-0770-8
Received:
Accepted:
Issue Date:
DOI: https://doi.org/10.1007/s00373-007-0770-8