Paper detail

Partitioning a graph into defensive k-alliances

A defensive $k$-alliance in a graph is a set $S$ of vertices with the property that every vertex in $S$ has at least $k$ more neighbors in $S$ than it has outside of $S$. A defensive $k$-alliance $S$ is called global if it forms a dominating set. In this paper we study the problem of partitioning the vertex set of a graph into (global) defensive $k$-alliances. The (global) defensive $k$-alliance partition number of a graph $Γ=(V,E)$, ($ψ_{k}^{gd}(Γ)$) $ψ_k^{d}(Γ)$, is defined to be the maximum number of sets in a partition of $V$ such that each set is a (global) defensive $k$-alliance. We obtain tight bounds on $ψ_k^{d}(Γ)$ and $ψ_{k}^{gd}(Γ)$ in terms of several parameters of the graph including the order, size, maximum and minimum degree, the algebraic connectivity and the isoperimetric number. Moreover, we study the close relationships that exist among partitions of $Γ_1\times Γ_2$ into (global) defensive $(k_1+k_2)$-alliances and partitions of $Γ_i$ into (global) defensive $k_i$-alliances, $i\in \{1,2\}$.