A new lower bound on the domination number of a graph

A set S of vertices in a graph G is a dominating set of G if every vertex not in S is adjacent to some vertex in S. The domination number, γ(G) , of G is the minimum cardinality of a dominating set of G. Lemańska (Discuss Math Graph Theory 24:165–170, 2004) showed that if T is a tree of order n≥ 2 with ℓ leaves, then γ(T) ≥ (n- ℓ+ 2) / 3 , and characterized all trees achieving equality in this bound. In this paper, we first characterize all trees T of order n with ℓ leaves satisfying γ(T) = ⌈ (n- ℓ+ 2) / 3 ⌉. We then generalize this result to connected graphs and show that if G is a connected graph of order n≥ 2 with k≥ 0 cycles and ℓ leaves, then γ(G) ≥ ⌈ (n- ℓ+ 2 - 2 k) / 3 ⌉. We also characterize the graphs G achieving equality for this new bound.