Boundary powerful k-alliances in graphs.
Ismael G. Yero, Juan Alberto Rodriguez-Velazquez · Ars Combinatoria · 2013
A global boundary defensive k-alliance in a graph G = (V,E) is a dominating set S of vertices of G with the property that every vertex in S has k more neighbors in S than it has outside of S. A global boundary offensive k-alliance in a graph G is a set S of vertices of G with the property that every vertex in V − S has k more neighbors in S than it has outside of S. We define a global boundary powerful k-alliance as a set S of vertices of G, which is both global boundary defensive k-alliance and global boundary offensive (k + 2)-alliance. In this paper we study mathematical properties of boundary powerful k-alliances. In particular, we obtain several bounds (closed formulas for the case of regular graphs) on the cardinality of every global boundary powerful k-alliance. In addition, we consider the case in which the vertex set of a graph G can be partitioned into two boundary powerful k-alliances, showing that, in such a case, k = −1 and, ifG is δ-regular, its algebraic connectivity is equal to δ + 1.