Independence and Domination Separation on Chessboard Graphs

R. Douglas Chatham1, Maureen Doyle2, Gerd H. Fricke1, Jon Reitmann1, R. Duane Skaggs1, Matthew Wolff3
1Department of Mathematics and Computer Science, Morehead State University, More- head, KY 40351 USA
2Department of Computer Science, Northern Kentucky University, Highland Heights, KY 41099 USA
3Pyramid Controls, Inc., Cincinnati, OH 45203 USA

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.