The domination number of cubic Hamiltonian graphs (Q2369389)

Let \(\gamma(G)\) denote the domination number of a graph \(G\). \textit{B. Reed} [Comb. Probab. Comput. 5, 277--295 (1996; Zbl 0857.05052)] conjectured that \(\gamma(G) \leq \lceil\frac{n}{3}\rceil\) if \(G\) is a connected cubic graph. In this paper it is proved that \(\lfloor\frac{n+2}{4}\rfloor \leq \gamma(G) \leq \lfloor\frac{n+1}{3}\rfloor\) for Hamiltonian cubic graphs \(G\) and that both bounds are sharp for all even \(n \geq 4\) where \(n\) is the order \(G\).