Domination of the rectangular queen's graph

Sándor Bozóki ; Péter Gál ; István Marosi ; William D. Weakley

The electronic journal of combinatorics, Tome 26 (2019) no. 4

Résumé

The queens 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 \leq m \leq n \leq 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. 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})$. Let $g(m)$ [respectively $g^{*}(m)$] be the largest integer such that $m$ queens suffice to dominate the $(m+1) \times g(m)$ board [respectively, to dominate the $(m+1) \times g^{*}(m)$ board with no two queens in a row]. Starting from the elementary bound $g(m) \leq 3m$, domination when the board is far from square is investigated. It is shown (Theorem 2) that $g(m) = 3m$ can only occur when $m \equiv 0, 1, 2, 3, \mbox{or } 4 \mbox{ (mod 9)}$, with an online appendix showing that this does occur for $m \leq 40, m \neq 3$. Also (Theorem 4), if $m \equiv 5, 6, \mbox{or } 7 \mbox{ (mod 9)}$ then $g^{*}(m) \leq 3m-2$, and if $m \equiv 8 \mbox{ (mod 9)}$ then $g^{*}(m) \leq 3m-4$. It is shown that equality holds in these bounds for $m \leq 40 $. Lower bounds on $\gamma(Q_{m \times n})$ are given. In particular, if $m \leq n$ then $\gamma(Q_{m \times n}) \geq \min \{ m,\lceil (m+n-2)/4 \rceil \}$. Two types of dominating sets (orthodox covers and centrally strong sets) are developed; each type is shown to give good upper bounds of $\gamma(Q_{m \times n})$ in several cases. Three questions are posed: whether monotonicity of $\gamma(Q_{m \times n})$ holds (other than from $(m, n) = (8, 11)$ to $(9, 11)$), whether $\gamma(Q_{m \times n}) = (m+n-2)/4$ occurs with $m \leq n < 3m+2$ (other than for $(m, n) = (3, 3)$ and $(11, 11)$), and whether the lower bound given above can be improved. 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 \leq m \leq n \leq 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})$.

Détail

DOI : 10.37236/6026

Classification : 05C69, 05B15
Mots-clés : \(m\) queens problem