Alliance Partition Number in Graphs

Abstract

Let $G$ be a graph with vertex set $V(G)$ and edge set $E(G)$. A (defensive) alliance in $G$ is a subset $S$ of $V(G)$ such that for every vertex $v\in S$, $|N(v)\cap S|\ge |N(v)\cap (V(G)–S)|$. The alliance partition number of a graph $G$, ${\psi }_a(G)$, is defined to be the maximum number of sets in a partition of $V(G)$ such that each set is a (defensive) alliance. In this paper, we give both general bounds and exact results for the alliance partition number of graphs, and in particular for regular graphs and trees.