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

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₄,C₅)-free if it has no induced 4-cycle or 5-cycle. Bruce Reed [14] 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) ≤ 1/8 (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₄,C₅)-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.