A Classification of Cactus Graphs According to their Domination Number

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. The authors proved in [A new lower bound on the domination number of a graph, J. Comb. Optim. 38 (2019) 721-738] that if G is a connected graph of order n ≥ 2 with k ≥ 0 cycles and l leaves, then γ(G) ≥ ?(n - l + 2 - 2k)/3?. As a consequence of the above bound, γ(G) = (n - l + 2(1 - k) + m)/3 for some integer m ≥ 0. In this paper, we characterize the class of cactus graphs achieving equality here, thereby providing a classification of all cactus graphs according to their domination number.