On domination in 2-connected cubic graphs
type: Item
instance of: scholarly article
title: On domination in 2-connected cubic graphs
zbMATH Open document ID: 1159.05043
author: B. Y. Stodolsky
published in: The Electronic Journal of Combinatorics
publication date: 2009-04-07T00:00:00Z
full work available at URL: https://eudml.org/doc/129771
full work available at URL: v15i1n38.html
review text: 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}\).
Mathematics Subject Classification ID: 05C69
Mathematics Subject Classification ID: 05C40
zbMATH DE Number: 5540900
zbMATH Keywords: domination number
zbMATH Keywords: cubic graphs
MaRDI profile type: Publication
description: scientific article; zbMATH DE number 5540900