On domination in 2-connected cubic graphs (Q1010698)

Summary: In 1996, \textit{B. Reed} [``Paths, stars, and the number three,'' Comb. Probab. Comput. 5, No.\,3, 277--295 (1996; Zbl 0857.05052)] 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 [\textit{A.V. Kostochka} and \textit{B.Y. Stodolsky}, ''On domination in connected cubic graphs,'' Discrete Math. 304. No.\,1-3, 45--50 (2005; Zbl 1077.05078)], 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}\frac{\gamma (G_k)}{|V(G_k)|} \geq\frac{1}{3}+\frac{1}{69}\). All the counter-examples, however, had cut-edges. On the other hand, in [\textit{A.V. Kostochka} and \textit{B.Y. Stodolsky}, ''An upper bound on domination number of \(n\)-vertex connected cubic graphs,'' Discrete Math. 309, No.\,5, 1142--1162 (2009; Zbl 1179.05083)] 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}\frac{\gamma(G_k)}{|V(G_k)|} \geq \frac{1}{3}+\frac{1}{78}\), and a sequence \(\{G_l'\}_{l=1}^{\infty}\) of connected cubic graphs where for each \(G_l'\) we have \(\frac{\gamma(G_l')}{|V(G_l')|} >\frac{1}{3}+\frac{1}{69}\).