The alliance partition number of grid graphs (Q2469300)

The concept of alliances in graphs was introduced by \textit{P. Kristiansen, S. M. Hedetniemi} and \textit{S. T. Hetedniemi} [J. Comb. Math. Comb. Comput. 48, 157--177 (2004; Zbl 1051.05068)]. For a graph \(G=(V,E)\), a non-empty subset \(S\subseteq V\) is called a defensive alliance if for each \(v\in S\), there are at least as many vertices from the closed neighborhood of \(v\) in \(S\) as in \(V-S\). The alliance partition number of \(G\), denoted by \(\psi _{a}(G)\) is the maximum cardinality of a partition of \(V\) into defensive alliances. In this paper the alliance partition number of grid graphs is determined. It is proved that for \(1\times c\) grid graph \(G_{1,c}\), \(\psi _{a}(G_{1,c})=\lceil (c+1)/2\rceil \) for \(c\geq 1\), \(\psi _{a}(G_{2,c})=c\) for any \(c>1\) and \(2\leq r\leq c\), \(\psi _{a}(G_{3,c})= c\) if \(c\) is odd and \(c+1\) if \(c\) is even if \(c\geq 3\) and \(\psi _{a}(G_{r,c})=\lfloor (r-2)/2\rfloor \lfloor (c-2)/2\rfloor +r+c-2\) for \(4\leq r\leq c\). Finally, some asymptotic results are derived.