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