06004152

j

06004152 Kr\'al', Daniel \v{S}koda, Petr Volec, Jan Domination number of cubic graphs with large girth. J. Graph Theory 69, No. 1-2, 131-142 (2012). 2012 John Wiley \& Sons, New York, NY EN domination dominating number cubic graphs probabilistic method Zbl 1162.05341

doi:10.1002/jgt.20568

Summary: We show that every $n$-vertex cubic graph with girth at least $g$ have domination number at most $0.299871n+ O(n/g)< 3n/10+ O(n/g)$ which improves a previous bound of $0.321216n+ O(n/g)$ by {\it D. Rautenbach} and {\it B. Reed} [``Domination in cubic graphs of large girth,'' Ito, Hiro (ed.) et al., Computational geometry and graph theory. International conference, KyotoCGGT 2007, Kyoto, Japan, 2007. Revised selected papers. Berlin: Springer. Lecture Notes in Computer Science 4535, 186--190 (2008; Zbl 1162.05341)].