Boundary Powerful \(k\)-alliances in Graphs

Abstract

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 \(\geq 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 \setminus 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. Additionally, 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, if \(G\) is \(\delta\)-regular, its algebraic connectivity is equal to \(\delta + 1\).