A new bound on the domination number of graphs with minimum degree two (Q625374)

Summary: For a graph \(G\), let \(\gamma(G)\) denote the domination number of \(G\) and let \(\delta(G)\) denote the minimum degree among the vertices of \(G\). A vertex \(x\) is called a bad-cut-vertex of \(G\) if \(G-x\) contains a component, \(C_x\), which is an induced 4-cycle and \(x\) is adjacent to at least one but at most three vertices on \(C_x\). A cycle \(C\) is called a special-cycle if \(C\) is a 5-cycle in \(G\) such that if \(u\) and \(v\) are consecutive vertices on \(C\), then at least one of \(u\) and \(v\) has degree 2 in \(G\). We let \(\text{bc}(G)\) denote the number of bad-cut-vertices in \(G\), and \(\text{sc}(G)\) the maximum number of vertex disjoint special-cycles in \(G\) that contain no bad-cut-vertices. We say that a graph is \((C_4, C_5)\)-free if it has no induced 4-cycle or 5-cycle. \textit{B. A. Reed} [Comb. Probab. Comput. 5, No. 3, 277--295 (1996; Zbl 0857.05052)] showed that if \(G\) is a graph of order \(n\) with \(\delta(G)\geq 3\), then \(\gamma(G)\leq 3n/8\). In this paper, we relax the minimum degree condition from three to two. Let \(G\) be a connected graph of order \(n\geq 14\) with \(\delta(G)\geq 2\). As an application of Reed's result, we show that \(\gamma(G) \leq \frac{1}{8}\left(3n+ \text{sc}(G)+ \text{bc}(G)\right)\). As a consequence of this result, we have that {\parindent=7mm \begin{itemize}\item[(i)]\(\gamma(G)\leq 2n/5\); \item[(ii)]if \(G\) contains no special-cycle and no bad-cut-vertex, then \(\gamma(G)\leq 3n/8\); \item[(iii)]if \(G\) is \((C_4,C_5)\)-free, then \(\gamma(G)\leq 3n/8\); \item[(iv)]if \(G\) is 2-connected and \(d_G(u)+ d_G(v)\geq 5\) for every two-adjacent vertices \(u\) and \(v\), then \(\gamma(G)\leq 3n/8\). \end{itemize}} All bounds are sharp.