A Lower Bound For Domination Numbers Of The Queen’s Graph

Abstract

The queen’s graph $Q_n$ has the squares of the $n\times n$ chessboard as its vertices; two squares are adjacent if they are in the same row, column, or diagonal. Let $\gamma (Q_n)$ be the minimum size of a dominating set of $Q_n$. Spencer proved that $\gamma (Q_n)\ge (n-1)/2$ for all $n$, and the author showed $\gamma (Q_n)=(n-1)/2$ implies $n\equiv 3(\mathrm{mod}4)$ and any minimum dominating set of $Q_n$ is independent.

Define a sequence by $n_1=3$, $n_2=11$, and for $i>2$, $n_i=4n_{i-1}–n_{i-2}–2$. We show that if $\gamma (Q_n)=(n-1)/2$ then $n$ is a member of the sequence other than $n_3=39$, and (counting from the center) the rows and columns occupied by any minimum dominating set of $Q_n$ are exactly the even-numbered ones. This improvement in the lower bound enables us to find the exact value of $\gamma (Q_n)$ for several $n$; $\gamma (Q_n)=(n+1)/2$ is shown here for $n=23,39$, and elsewhere for $n=27,71,91,115,131$.