A New Bound on the Domination Number of Graphs with Minimum Degree Two - Henning, Michael A.; Schiermeyer, Ingo; Yeo, Anders (The Electronic Journal of Combinatorics, 2011)
For a graph G, let γ(G) denote the domination number of G and let δ(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 bc(G) denote the number of bad-cut-vertices in G, and 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. Bruce Reed [Paths, stars and the number three. Combin. Probab. Comput. 5 (1996), 277–295] showed that if G is a graph of order n with δ(G) 3, then γ(G) 3n/8. In this paper, we relax the minimum degree condition from three to two. Let G be a connected graph of order n 14 with δ(G) 2. As an application of Reed’s result, we show that γ(G) 18 ( 3n + sc(G) + bc(G)). As a consequence of this result, we have that (i) γ(G) 2n/5; (ii) if G contains no special-cycle and no bad-cut-vertex, then γ(G) 3n/8; (iii) if G is (C_4,C_5)-free, then γ(G) 3n/8; (iv) if G is 2-connected and d_G(u) + d_G(v) 5 for every two adjacent vertices u and v, then γ(G) 3n/8. All bounds are sharp.