Menu
The queen’s graph \(Q_n\) has the squares of the \(n \times n\) chessboard as its vertices; two squares are adjacent if they are in the same row, column, or diagonal. Let \(\gamma(Q_n)\) be the minimum size of a dominating set of \(Q_n\). Spencer proved that \(\gamma(Q_n) \geq {(n-1)}/{2}\) for all \(n\), and the author showed \(\gamma(Q_n) = {(n-1)}/{2}\) implies \(n \equiv 3 \pmod{4}\) and any minimum dominating set of \(Q_n\) is independent.
Define a sequence by \(n_1 = 3\), \(n_2 = 11\), and for \(i > 2\), \(n_i = 4n_{i-1} – n_{i-2} – 2\). We show that if \(\gamma(Q_n) = {(n-1)}/{2}\) then \(n\) is a member of the sequence other than \(n_3 = 39\), and (counting from the center) the rows and columns occupied by any minimum dominating set of \(Q_n\) are exactly the even-numbered ones. This improvement in the lower bound enables us to find the exact value of \(\gamma(Q_n)\) for several \(n\); \(\gamma(Q_n) = {(n+1)}/{2}\) is shown here for \(n = 23, 39\), and elsewhere for \(n = 27, 71, 91, 115, 131\).