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| \geq |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.