Discrete Mathematics and Optimization Seminar

---

DIETER RAUTENBACH
University of Bonn
Monday February 26th at 4.30pm
Burnside 1205



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

Abstract. We prove that for graphs of order $n$, minimum degree $\delta\geq 2$ and girth $g\geq 5$ the domination number $\gamma$ 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\geq 5$ the domination number $\gamma$ satisfies $\gamma \leq \left(\frac{44}{135}+\frac{82}{135g}\right)n$
which improves recent results due to Kostochka and Stodolsky (2005) and Kawarabayashi, Plummer and Saito (2006)
for large enough girth. Furthermore, it confirms a conjecture of Reed about cubic graphs which turned out to be false in general for graphs of girth at least 83.
(This is joint work with Christian Loewenstein.)