\documentclass[12pt]{article}
\usepackage{amsmath,mathrsfs,bbm}
\usepackage{amssymb}
\textwidth=4.825in
\overfullrule=0pt
\thispagestyle{empty}
\begin{document}
\noindent
%
%
{\bf Michael A. Henning, Ingo Schiermeyer and Anders Yeo}
%
%
\medskip
\noindent
%
%
{\bf A New Bound on the Domination Number of Graphs with Minimum Degree Two}
%
%
\vskip 5mm
\noindent
%
%
%
%
For a graph $G$, let $\gamma(G)$ denote the domination number of $G$
and let $\delta(G)$ denote the minimum degree among the vertices of
$G$. A vertex $x$ is called a bad-cut-vertex of $G$ if $G-x$ contains
a component, $C_x$, which is an induced $4$-cycle and $x$ is adjacent
to at least one but at most three vertices on $C_x$. A cycle $C$ is
called a special-cycle if $C$ is a $5$-cycle in $G$ such that if $u$
and $v$ are consecutive vertices on $C$, then at least one of $u$ and
$v$ has degree~$2$ in $G$. We let ${\rm bc}(G)$ denote the number of
bad-cut-vertices in~$G$, and ${\rm sc}(G)$ the maximum number of
vertex disjoint special-cycles in~$G$ that contain no
bad-cut-vertices. We say that a graph is $(C_4,C_5)$-free if it has no
induced $4$-cycle or $5$-cycle. Bruce Reed [Paths, stars and the
number three. Combin. Probab. Comput. 5 (1996), 277--295] showed that
if $G$ is a graph of order~$n$ with $\delta(G) \ge 3$, then $\gamma(G)
\le 3n/8$. In this paper, we relax the minimum degree condition from
three to two. Let $G$ be a connected graph of order~$n \ge 14$ with
$\delta(G) \ge 2$. As an application of Reed's result, we show that
$\gamma(G) \le \frac{1}{8} ( 3n + {\rm sc}(G) + {\rm bc}(G))$. As a
consequence of this result, we have that (i) $\gamma(G) \le 2n/5$;
(ii) if $G$ contains no special-cycle and no bad-cut-vertex, then
$\gamma(G) \le 3n/8$; (iii) if $G$ is $(C_4,C_5)$-free, then
$\gamma(G) \le 3n/8$; (iv) if $G$ is $2$-connected and $d_G(u) +
d_G(v) \ge 5$ for every two adjacent vertices $u$ and $v$, then
$\gamma(G) \le 3n/8$. All bounds are sharp.
\end{document}