Leaper Embeddings

Abstract

A leaper is a chess piece which generalises the knight. Given $n$ and a $(p,q)$-leaper $L$, we study the greatest $m$ such that the $m\times m$ grid graph can be embedded into the $n\times n$ leaper graph of $L$. We can assume that $p$ and $q$ are relatively prime. We show that $m\approx n$ when $p$ and $q$ are of opposite parities and $m\approx n/2$ otherwise. The latter case is substantially more difficult. The proof involves certain combinatorial-geometric results on the chords of connected figures which might be of independent interest.

12 pages, 9 figures