Domination of the rectangular queen's graph

Abstract

The queens graph Qm×n has the squares of the m × 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 Qm×n is a dominating set for Qm×n if every square of Qm×n is either in D or adjacent to a square in D. The minimum size of a dominating set of Qm×n is the domination number, denoted by γ(Qm×n). Values of γ(Qm×n), 4 6 m 6 n 6 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: γ(Q8×11) = 6 > 5 = γ(Q9×11) = γ(Q10×11) = γ(Q11×11). Let g(m) [respectively g ∗ (m)] be the largest integer such that m queens suffice to dominate the (m+1)×g(m) board [respectively, to dominate the (m+1)×g ∗ (m) board with no two queens in a row]. Starting from the elementary bound g(m) 6 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 ≡ 0, 1, 2, 3, or 4 (mod 9), with the online appendix showing that this does occur for m 6 40, m 6= 3. Also (Theorem 4), if m ≡ 5, 6, or 7 (mod 9) then g ∗ (m) 6 3m − 2, and if m ≡ 8 (mod 9) then g ∗ (m) 6 3m − 4. It is shown that equality holds in these bounds for m 6 40. Lower bounds on γ(Qm×n) are given. In particular, if m 6 n then γ(Qm×n) > min{m, d(m + n − 2)/4e}. Two types of dominating sets (orthodox covers and centrally strong sets) are developed; each type is shown to give good upper bounds of γ(Qm×n) in several cases. Three questions are posed: whether monotonicity of γ(Qm×n) holds (other than from (m, n) = (8, 11) to (9, 11)), whether γ(Qm×n) = (m + n − 2)/4 occurs with m 6 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 Qm×n is the independent domination number, denoted by i(Qm×n). Values of i(Qm×n), 4 6 m 6 n 6 18, are given here, in each case with some minimum dominating sets. In these ranges for m and n, monotonicity fails twice: i(Q8×11) = 6 > 5 = i(Q9×11) = i(Q10×11) = i(Q11×11), and i(Q11×18) = 9 > 8 = i(Q12×18).