A proof of the $\frac{3}{8}$-conjecture for independent domination in cubic graphs

Abstract

A set $S$ of vertices in a graph $G$ is a dominating set of $G$ if every vertex not in $S$ is adjacent to a vertex in~$S$. An independent dominating set in $G$ is a dominating set of $G$ with the additional property that it is an independent set. The domination number, $\gamma (G)$, and the independent domination number, $i(G)$, are the minimum cardinalities among all dominating sets and independent dominating sets in $G$, respectively. By definition, $\gamma (G)\le i(G)$ for all graphs $G$. Let $G$ be a connected cubic graph of order~$n$. In 1996 Reed [Combin.\ Probab.\ Comput.\ 5 (1996), 277--295] proved a breakthrough result that $\gamma (G)\le \frac{3}{8}n$. We prove the stronger result that if $G$ is different from $K_{3,3}$ and the $5$-prism $C_5\square K_2$, then $i(G)\le \frac{3}{8}n$. This proves a known conjecture. The bound is tight in the sense that there are infinite families of connected cubic graphs that achieve equality in this bound.

49 pages, 56 figures