Global defensive alliances of trees and Cartesian product of paths and cycles

Given a graph $G$, a defensive alliance of $G$ is a set of vertices $S?V\left(G\right)$ satisfying the condition that for each $v\in S$, at least half of the vertices in the closed neighborhood of $v$ are in $S$. A defensive alliance $S$ is called global if every vertex in $V\left(G\right)?S$ is adjacent to at least one member of the defensive alliance $S$. The global defensive alliance number of $G$, denoted ${\gamma }_a\left(G\right)$, is the minimum size around all the global defensive alliances of $G$. In this paper, we present an efficient algorithm to determine the global defensive alliance numbers of trees, and further give formulas to decide the global defensive alliance numbers of complete $k$-ary trees for $k=2,3,4$. We also establish upper bounds and lower bounds for ${\gamma }_a(P_m\times P_n),{\gamma }_a(C_m\times P_n)$ and ${\gamma }_a(C_m\times C_n)$, and show that the bounds are sharp for certain $m,n$.