Upper bounds for domination numbers of the queen's graph (Q5957757)

\(\gamma(Q_n)\) and \(i(Q_n)\) are the minimum sizes of a dominating set and an independent dominating set of the queen's graph \(Q_n\), respectively. The great majority of recent work on queen domination uses monochromatic sets, either to establish exact values or upper bounds. In this paper the author examines the most commonly used types of monochromatic dominating sets, which he calls \(p\)-covers, where \(p \in \{0,1\}\). He characterises \(p\)-covers in terms of occupied diagonals, dividing them into types A and B. He provides evidence that type A \(p\)-covers are probably more useful in the search for minimum dominating sets, and relates \(p\)-covers to some dichromatic minimum dominating sets of \textit{W. Ahrens} [``Mathematische Unterhaltungen und Spiele'' (B. G. Teubner, Leipzig-Berlin) (1910)] using the function \(h(x,y) = (2(x+y), 2(y-x))\). In the rest of the paper the author develops a general method, involving a block replacement technique, of providing upper bounds for the queen domination numbers. In particular, in a corollary to the main technical theorem, he shows that, if \(n \equiv 1 \pmod{4}\) and there exists a \(d\)-element type A \(0\)-cover \(D\) of \(Q_n\), then for all \(k\), \(\gamma(Q_k) \leq (d+3)k/(n+2)+O(1)\). If \(D\) is independent, then for all \(k\), \(i(Q_k) \leq (d+6)k/(n+2)+O(1)\). Further corollaries give the improved general bounds \(\gamma(Q_k) \leq 34k/63+O(1) < 0.54k + O(1)\) and \(i(Q_k) \leq 19k/33+O(1) < 0.\overline{57}k + O(1)\), and show that the construction sometimes gives minimum dominating sets.