Queens graphs for chessboards on the torus (Q2760445)

Although combinatorial problems on chessboards have been studied for almost 150 years, it is only recently that we have begun studying the placement of chess pieces on toroidal chessboards. In this paper the authors examine \(Q_n^t\), the queens graph obtained from an \(n \times n\) chessboard on the torus. In particular they obtain the first set of results for the domination, independent domination and independence numbers of \(Q_n^t\) (which are denoted by \(\gamma(Q_n^t)\), \(i(Q_n^t)\) and \(\beta(Q_n^t)\), respectively). For \(\beta(Q_n^t)\) they show that \(\beta(Q_n^t) = n\) for \(n \equiv 1, 5 \pmod{6}\), \(\beta(Q_n^t) = n-1\) for \(n \equiv 2, 10 \pmod{12}\), and \(\beta(Q_n^t) \leq n-1\) for \(n \equiv 3, 6 \pmod{9}\). They have not yet established a general lower bound for \(n \equiv i \pmod{12}\), where \(i \in \{0,3,4,6,8,9\}\), but have computed \(\beta(Q_n^t)\) for small values of \(n\). For these small values of \(n\) it can be seen that \(\beta(Q_n^t) = n-2\) for \(n \in \{0,3,4,6,8,9\}\), but it is not known whether this is true in general. For the domination problem the authors have shown that if \(n \equiv 3,5,21,33 \pmod{36}\) then \(\gamma(Q_n^t) = i(Q_n^t) = n/3\), and if \(n \equiv 6,30 \pmod{36}\) then \(\gamma(Q_n^t) = n/3 +1\) and \(i(Q_n^t) \leq n/3 +3\). Exact values of \(\gamma(Q_n^t)\) and \(i(Q_n^t)\) for some small values of \(n\) are listed in the paper and from this two interesting facts emerge. All three possibilities \(i(Q_n^t) = i(Q_n)\), \(i(Q_n^t) < i(Q_n)\) and \(i(Q_n^t) > i(Q_n)\) occur, and neither \(\gamma(Q_n^t)\) nor \(i(Q_n^t)\) is monotone. These observations and others lead to a raft of open problems in this fertile new area.