×

A new bound on the domination number of graphs with minimum degree two. (English) Zbl 1209.05171

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. 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
(i)
\(\gamma(G)\leq 2n/5\);
(ii)
if \(G\) contains no special-cycle and no bad-cut-vertex, then \(\gamma(G)\leq 3n/8\);
(iii)
if \(G\) is \((C_4,C_5)\)-free, then \(\gamma(G)\leq 3n/8\);
(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\).
All bounds are sharp.

MSC:

05C69 Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.)

Citations:

Zbl 0857.05052
PDFBibTeX XMLCite
Full Text: EuDML EMIS