Global Alliance Partition in Trees

Abstract

Let $G$ be a connected 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, ${\psi }_a(G)$, was defined (and further studied in [11]) to be the maximum number of sets in a partition of $V(G)$ such that each set is a (defensive) alliance. Similarly, ${\psi }_g(G)$ is the maximum number of sets in a partition of $V(G)$ such that each set is a global alliance, i.e., each set is an alliance and a dominating set. In this paper, we give bounds for the global alliance partition number in terms of the minimum degree, which gives exactly two values for ${\psi }_g(G)$ in trees. We concentrate on conditions that classify trees to have ${\psi }_g(G)=i$ ($i=1,2$), presenting a characterization for binary trees.