Saturated boundary kk-alliances in graphs

In this paper, we introduce a new concept of saturated vertices for the alliances. For a given graph G=(V,E)G=(V,E) and S⊂VS⊂V, a vertex v∈Vv∈V is said to be SS-saturated  , if the number of its defenders is equal to the number of its attackers for SS. We define new parameters |λ(S)||λ(S)| and |λ̄(S)| as the number of SS-saturated vertices and not SS-saturated vertices of SS, respectively. We study mathematical properties of (global) saturated boundary defensive, offensive and powerful kk-alliances and theoretical results are obtained by giving in particular some tight bounds and exact values on the cardinality of such alliances. As a main result, we give tight bounds for the cardinality of every minimal global boundary powerful (−1)(−1)-alliance (MGBPA) in terms only of the order and the size of graph. Furthermore, we establish two algorithms which generate graphs containing (connected) MGBPA from a given complete graph K2nK2n.