Global defensive sets in graphs

In the paper we study a new problem of finding a minimum global defensive set in a graph which is a generalization of the global alliance problem. For a given graph GG and a subset SS of a vertex set of GG, we define for every subset XX of SS the predicate SEC(X)=trueSEC(X)=true if and only if |N[X]∩S|≥|N[X]∖S||N[X]∩S|≥|N[X]∖S| holds, where N[X]N[X] is a closed neighbourhood of XX in graph GG. A set SS is a defensive alliance   if and only if for each vertex v∈Sv∈S we have SEC({v})=trueSEC({v})=true. If SS is also a dominating set of GG (i.e.,  N[S]=V(G)N[S]=V(G)), we say that SS is a global defensive alliance.We introduce the concept of defensive sets in graph GG as follows: set SS is a defensive set   in GG if and only if for each vertex v∈Sv∈S we have SEC({v})=trueSEC({v})=true or there exists a neighbour uu of vv such that u∈Su∈S and SEC({v,u})=trueSEC({v,u})=true. Similarly, if SS is also a dominating set of GG, we say that SS is a global defensive set. We also study the problems of total dominating alliances (total alliances) and total dominating defensive sets (total defensive sets  ), i.e.,  SS is a dominating set and the induced graph G[S]G[S] has no isolated vertices.In the paper we proved the NPNP-completeness for planar bipartite subcubic graphs of the decision versions of the following minimalization problems: a global and total alliance, a global and total defensive set. We proposed polynomial time algorithms solving in trees the problem of finding the minimum total and global defensive set and the total alliance. We obtained the lower bound on the minimum size of a global defensive set in arbitrary graphs and trees.