A note on global alliances in trees
Mohamed Bouzefrane, Mustapha Chellali · Opuscula Mathematica · 2011
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 (respectively, defensive) alliance if for each vertex in V -S (respectively, in S) at least half the vertices from the closed neighborhood of v 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) (respectively, global defensive alliance number γa(G)) is the minimum cardinality of a global offensive alliance (respectively, global deffensive alliance) of G.We show that if T is a tree of order n, then γo(T ) ≤ 2γ(T ) -1 and if n ≥ 3, then γo(T ) ≤ 3 2 γa(T ) -1.Moreover, all extremal trees attaining the first bound are characterized.