×

Independence and domination separation on chessboard graphs. (English) Zbl 1176.05051

Summary: A legal placement of Queens is any placement of Queens on an order \(N\) chessboard in which any two attacking Queens can be separated by a Pawn. The Queens independence separation number is the minimum number of Pawns which can be placed on an \(N\times N\) board to result in a separated board on which a maximum of \(m\) independent Queens can be placed. We prove that \(N+k\) Queens can be separated by \(k\) Pawns for large enough \(N\) and provide some results on the number of fundamental solutions to this problem. We also introduce separation relative to other domination-related parameters for Queens, Rooks, and Bishops.

MSC:

05C69 Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.)
68R10 Graph theory (including graph drawing) in computer science