\magnification=1200
\hsize=4in
\overfullrule=0pt
\input amssym
%\def\frac#1 #2 {{#1\over #2}}
\def\emph#1{{\it #1}}
\def\em{\it}
\nopagenumbers
\noindent
%
%
{\bf B. Y. Stodolsky}
%
%
\medskip
\noindent
%
%
{\bf On Domination in 2-Connected Cubic Graphs}
%
%
\vskip 5mm
\noindent
%
%
%
%
In 1996, Reed proved that the domination number, $\gamma(G)$, of every
$n$-vertex graph $G$ with minimum degree at least $3$ is at most
$3n/8$ and conjectured that $\gamma(H)\leq\lceil n/3\rceil$ for every
connected $3$-regular (cubic) $n$-vertex graph $H$. In [1] this
conjecture was disproved by presenting a connected cubic graph $G$ on
$60$ vertices with $\gamma(G)=21$ and a sequence
$\{G_k\}_{k=1}^{\infty}$ of connected cubic graphs with
$\lim_{k\to\infty}{\gamma(G_k)\over|V(G_k)|}
\geq{1\over3}+{1\over69}$. All the counter-examples,
however, had cut-edges. On the other hand, in [2] it was
proved that $\gamma(G)\leq\ 4n/11$ for every connected cubic $n$-vertex
graph $G$ with at least $10$ vertices. In this note we construct a
sequence of graphs $\{G_k\}_{k=1}^{\infty}$ of $2$-connected cubic
graphs with $\lim_{k\to\infty}{\gamma(G_k)\over|V(G_k)|}
\geq{1\over3}+{1\over78}$, and a sequence
$\{G_l'\}_{l=1}^{\infty}$ of connected cubic graphs where for each
$G_l'$ we have ${\gamma(G_l')\over|V(G_l')|}
>{1\over3}+{1\over69}$.

\bye

.
