Irredundance and domination in kings graphs Original Research Article

Each king on an n×n chessboard is said to attack its own square and its neighboring squares, i.e., the nine or fewer squares within one move of the king. A set of kings is said to form an irredundant set if each attacks a square attacked by no other king in the set. We prove that the maximum size of an irredundant set of kings is bounded between (n−1)2/3 and n2/3, and that the minimum size of a maximal irredundant set of kings is bounded between n2/9 and ⌊(n+2)/3⌋2, where the latter upper and lower bounds are in fact equal when n≡0 (mod 3). Results are given for related domination and independence problems.