Chessboard domination problems (Q1174120)

The classical problems of covering chessboards with the minimum number of chess pieces were important in motivating the revival of the study of dominating sets in graphs, which commenced in the early 1970's. These problems certainly date back to de Jaenisch and have been mentioned in the literature frequently since that time. A graph \(P_ n\) may be formed from an \(n\times n\) chessboard and a chess piece \(P\) by taking the \(n^ 2\) squares of the board as vertices and two vertices are adjacent if piece \(P\) situated at one of the squares is able to move directly to the other. For example the Queen's graph \(Q_ n\) has the \(n^ 2\) squares as vertices and squares are adjacent if they are on the same line (row, column or diagonal). In this paper we survey recent results which involve various domination parameters for graphs which are constructed in this way. Outlines of some of the proofs are given, although most appear elsewhere.