Domination of the rectangular queen's graph (Q2278125): Difference between revisions

Summary: 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^\ast(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^\ast(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\), or \(4 \pmod 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\), or \(7 \pmod 9\) then \(g^\ast(m) \leq 3m-2\), and if \(m \equiv 8 \pmod 9\) then \(g^\ast(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})\).