Menu
A defensive alliance in a graph \( G(V,E) \) is a set of vertices \( S \subseteq V \) such that for every vertex \( v \in S \), the closed neighborhood \( N_G[v] \) of \( v \) has at least as many vertices in \( S \) as it has in \( V – S \). An offensive alliance is a set of vertices \( S \subseteq V \), such that for every vertex \( v \) in the boundary \( \partial(S) \) of \( S \) the number of neighbors that \( v \) has in \( S \) is greater than or equal to the number of neighbors it has in \( V – S \). A subset of vertices which is both an offensive and a defensive alliance is called a powerful alliance. An alliance which is also a dominating set is called a global alliance. In this paper, we show that finding an optimal defensive (offensive, powerful) global alliance is an NP-hard problem.