On domination in 2-connected cubic graphs

B. Y. Stodolsky

The electronic journal of combinatorics, Tome 15 (2008)

Résumé

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}$.

Détail

DOI : 10.37236/913

Classification : 05C69, 05C40
Mots-clés : domination number, cubic graphs