Values of domination numbers of the queen's graph (Q5942492)

The queen's graph \(Q_n\) has the squares of the \(n \times n\) chessboard as its vertices, with two squares being adjacent if they are in the same row, column or diagonal. \(\gamma(Q_n)\) and \(i(Q_n)\) are defined to be the minimum sizes of a dominating set and an independent dominating set of \(Q_n\) respectively. The authors establish the following new values and bounds for these parameters: (i) \(\gamma(Q_n) = \lceil n/2 \rceil\) for 17 new values of \(n\) (which implies, in particular, that the set of values for which the conjecture \(\gamma(Q_{4k+1})=2k+1\) is known to hold is extended to \(k \leq 32\)); (ii) \(i(Q_n) = \lceil n/2 \rceil\) for 11 new values of \(n\), including \(5\) of those from (i); (iii) one or both of \(\gamma(Q_n)\) and \(i(Q_n)\) is shown to lie in \(\{\lceil n/2 \rceil, \lceil n/2 \rceil + 1\}\) for \(85\) values of \(n\) distinct from those in (i) and (ii). When combined with previous work, these results imply that for \(n \leq 120\), each of \(\gamma(Q_n)\) and \(i(Q_n)\) is either known, or known to have one of two values. The authors also establish the general bounds \(\gamma(Q_n) \leq 69n/133 + O(1)\) and \(i(Q_n) \leq 61n/111 + O(1)\), an improvement on the best previously published upper bounds of \(\gamma(Q_n) \leq 8n/15 + O(1)\) and \(i(Q_n) \leq 19n/33 + O(1)\). The results are established by the use of so-called \(p\)-covers, with slight variations. In such a cover the queens are required to occupy certain prescribed lines along with a few others if the cover size exceeds \((n-1)/2\). For these other lines the second author's parallelogram law [in \textit{W. D. Weakley}, ``A lower bound for domination numbers of the queen's graph'', submitted] greatly restricts the possibilities that need to be considered. For \(n \leq 35\) straightforward hand calculation suffices to either find corresponding dominating sets, or to show that none exist. For large \(n\) the authors use a computer search which makes use of a very fast program developed by \textit{D. E. Knuth} [in ``Dancing links'', in Millenial Perspectives in Computer Science, J. Davies, B. Roscoe and J. Woodcock (editors), 187-214 (Palgrave, Hound-mills, 2000)] for the exact cover problem.