Queen Domination of Even Square Boards

Abstract

The queen's graph $Q_{m \times n}$ has the squares of the $m \times n$ chessboard as its vertices; we identify the $m \times n$ chessboard with a rectangle of width $m$ and height $n$ in the Cartesian plane, having sides parallel to the coordinate axes and placed so that square centers have integer coordinates. Two squares are adjacent if they are in the same row, column, or diagonal of the board. A set $D$ of squares of $Q_{m \times n}$ is a dominating set for $Q_{m \times n}$ if every square of $Q_{m \times n}$ is either in $D$ or adjacent to a square in $D$. The minimum size of a dominating set of $Q_{m \times n}$ is the domination number, denoted by $\gamma(Q_{m \times n})$.

We give a new proof of the bound $\gamma(Q_{m \times n}) \geq \min \left\{m, n, \left\lceil \frac{m+n-2}{4} \right\rceil\right\}$, with implications for queen domination problems, and then consider square boards.

Let $n$ be an even integer and assume $Q_{n \times n}$ has a dominating set $D$ of size $n/2$ (which implies $\gamma(Q_{n \times n}) = n/2$). For $p \in \{ 0, 1 \}$, let $D_{p} = \{ (x, y) \in D \mbox{ : } x + y \equiv p \mbox{ (mod 2)}\}$. Say that $D$ is monochromatic if $D = D_{p}$ for some $p$; otherwise bichromatic. We show that if $D$ is bichromatic then $||D_{0}| - |D_{1}|| \leq 2$ and conjecture that if $n > 4$ then $D$ is monochromatic.

Assume further that $D$ is monochromatic. If $n \equiv 0 \mbox{ (mod 4)}$ then $n \in \{ 4, 12 \}$. If $n \equiv 2 \mbox{ (mod 4)}$ then odd integers $k = n/2, e, d$ with $1 \leq d, e \leq k$ satisfy the equation $d^{2} + (k-1)e^{2} = k(k^{2} + 2)/3$. We analyze six infinite sequences of solutions of this equation arising from Fermat-Pell equations, give monochromatic dominating sets of $Q_{n \times n}$ of size $n/2$ for $n = 2, 4, 6, 10, 12, 18, 30 \text{ (new)}$, and $130$, and show there are no others with $n < 238$.