Cops and robbers on chess graphs

Abstract

Cops and robbers is a pursuit-evasion game played on graphs. We completely classify the cop numbers for $n\times n$ knight graphs and queen graphs. This completes the classification of the cop numbers for all $n\times n$ classical chess graphs. As a corollary, we resolve an open problem about the monotonicity of $c$(${\mathcal{Q}}_n$). Moreover, we introduce \emph{royal graphs}, a generalization of chess graphs for arbitrary piece movements, which models real-life movement constraints. We give results on the cop numbers for these families.

10 pages, 2 figures