Domination of the rectangular queen's graph

Abstract

The queen's graph $Q_{m\times n}$ has the squares of the $m\times n$ chessboard as its vertices; 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})$. Values of $\gamma (Q_{m\times n}),4\le m\le n\le 18,$ are given here, in each case with a file of minimum dominating sets (often all of them, up to symmetry) in an online appendix at https://www.combinatorics.org/ojs/index.php/eljc/article/view/v26i4p45/HTML. In these ranges for $m$ and $n$, monotonicity fails once: $\gamma (Q_{8\times 11})=6>5=\gamma (Q_{9\times 11})=\gamma (Q_{10\times 11})=\gamma (Q_{11\times 11})$. Lower bounds on $\gamma (Q_{m\times n})$ are given. In particular, if $m\le n$ then $\gamma (Q_{m\times n})\ge \min \{m,\lceil (m+n-2)/4\rceil \}$. A set of squares is independent if no two of its squares are adjacent. The minimum size of an independent dominating set of $Q_{m\times n}$ is the independent domination number, denoted by $i(Q_{m\times n})$. Values of $i(Q_{m\times n}),4\le m\le n\le 18,$ are given here, in each case with some minimum dominating sets. In these ranges for $m$ and $n$, monotonicity fails twice: $i(Q_{8\times 11})=6>5=i(Q_{9\times 11})=i(Q_{10\times 11})=i(Q_{11\times 11})$, and $i(Q_{11\times 18})=9>8=i(Q_{12\times 18})$.