A lower bound on the global powerful alliance number in trees
Saliha Ouatiki, Mohamed Bouzefrane · RAIRO - Operations Research · 2021
For a graph G = (V, E), a set D ⊆ V is a dominating set if every vertex in V − D is either in D or has a neighbor in D. A dominating set D is a global offensive alliance (resp. a global defensive alliance) if for each vertex v in V − D (resp. v in D) at least half the vertices from the closed neighborhood of v are in D. A global powerful alliance is both global defensive and global offensive. The global powerful alliance number γpa(G) is the minimum cardinality of a global powerful alliance of G. We show that if T is a tree of order n with l leaves and s support vertices, then $ {\gamma }_{{pa}}(T)\enspace \ge \enspace \frac{3n-2l-s+2\enspace }{5}$ . Moreover, we provide a constructive characterization of all extremal trees attaining this bound.