Strategic balance in graphs

For a given graph GG, a nonempty subset SS contained in V(G)V(G) is an alliance   iff for each vertex v∈Sv∈S there are at least as many vertices from the closed neighbourhood of vv in SS as in V(G)−SV(G)−S. An alliance is global   if it is also a dominating set of GG. The alliance partition number   of GG was defined in Hedetniemi et al. (2004) to be the maximum number of sets in a partition of V(G)V(G) such that each set is an alliance. Similarly, in Eroh and Gera (2008) the global alliance partition number is defined for global alliances, where the authors studied the problem for (binary) trees.In the paper we introduce a new concept of strategic balance   in graphs: for a given graph GG, determine whether there is a partition of vertex set V(G)V(G) into three subsets NN, SS and II such that both NN and SS are global alliances. We give a survey of its general properties, e.g., showing that a graph GG has a strategic balance iff its global alliance partition number equals at least 2. We construct a linear time algorithm for solving the problem in trees (thus giving an answer to the open question stated in Eroh and Gera (2008)) and studied this problem for many classes of graphs: paths, cycles, wheels, stars, complete graphs and complete kk-partite graphs. Moreover, we prove that this problem is NPNP-complete for graphs with a degree bounded by 4 and state an open question regarding subcubic graphs.