Global defensive sets in graphs

• Published in: Discrete mathematics 2016-07, Vol.339 (7), p.1861-1870
• Main Authors: Lewona, Robert, Malafiejskab, Anna, Malafiejskia, Michal
• Format: Article
• Language: English
• Subjects: [formula omitted]-completeness; Algorithms; Alliance; Defensive set; Domination; Graph theory; Graphs; Lower bounds; Mathematical analysis; Trees
• ISSN: 0012-365X; 1872-681X
• DOI: 10.1016/j.disc.2016.01.022

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 G and a subset S of a vertex set of G, we define for every subset X of S the predicate SEC(X)=true if and only if |N[X]∩S|≥|N[X]∖S| holds, where N[X] is a closed neighbourhood of X in graph G. A set S is a defensive alliance if and only if for each vertex v∈S we have SEC({v})=true. If S is also a dominating set of G (i.e.,  N[S]=V(G)), we say that S is a global defensive alliance. We introduce the concept of defensive sets in graph G as follows: set S is a defensive set in G if and only if for each vertex v∈S we have SEC({v})=true or there exists a neighbour u of v such that u∈S and SEC({v,u})=true. Similarly, if S is also a dominating set of G, we say that S 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.,  S is a dominating set and the induced graph G[S] has no isolated vertices. In the paper we proved the NP-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.