The alliance partition number of grid graphs (Q2469300)

From MaRDI portal
scientific article
Language Label Description Also known as
English
The alliance partition number of grid graphs
scientific article

    Statements

    The alliance partition number of grid graphs (English)
    0 references
    0 references
    0 references
    5 February 2008
    0 references
    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.
    0 references
    0 references
    defensive alliance
    0 references
    alliance partition
    0 references
    alliance partition number
    0 references
    grid graph
    0 references
    0 references