Domination and irredundance in the queens' graph (Q1356524): Difference between revisions

The vertices of the queens' graph \(Q_n\) are the squares of an \(n\times n\) chessboard and two squares are adjacent if a queen placed on one covers the other. This paper shows that the domination number of \(Q_n\) is at most \(31n/54+ O(1)\), that \(Q_n\) possesses minimal dominating sets of cardinality \(5n/2- O(1)\) and that the cardinality of any irredundant set of vertices of \(Q_n\) \((n\geq q)\) is at most \(\lfloor 6n+6-8\sqrt{n+\sqrt n+1}\rfloor\).