On the global offensive alliance number of a tree
Mohamed Bouzefrane, Mustapha Chellali · Opuscula Mathematica · 2009
For a graph G = (V, E), a set S ⊆ V is a dominating set if every vertex in V -S has at least a neighbor in S. A dominating set S is a global offensive alliance if for every vertex v in V -S, at least half of the vertices in its closed neighborhood are in S. The domination number γ(G) is the minimum cardinality of a dominating set of G and the global offensive alliance number γo(G) is the minimum cardinality of a global offensive alliance of G.We first show that every tree of order at least three with ℓ leaves and s support vertices satisfies γo(T ) ≥ (n -ℓ + s + 1)/3 and we characterize extremal trees attaining this lower bound.Then we give a constructive characterization of trees with equal domination and global offensive alliance numbers.