Independence and Domination Separation on Chessboard Graphs

Abstract

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.