Leaper graphs
| dc.creator | Knuth, Donald E. | |
| dc.date | 1994-11-01 | |
| dc.date.accessioned | 2026-07-07T09:15:13Z | |
| dc.date.available | 2026-07-07T09:15:13Z | |
| dc.description | An $\{r,s\}$-leaper is a generalized knight that can jump from $(x,y)$ to $(x\pm r,y\pm s)$ or $(x\pm s,y\pm r)$ on a rectangular grid. The graph of an $\{r,s\}$-leaper on an $m\times n$ board is the set of $mn$~vertices $(x,y)$ for $0\leq x<m$ and $0\leq y<n$, with an edge between vertices that are one $\{r,s\}$-leaper move apart. We call $x$ the {\it rank} and $y$ the {\it file} of board position $(x,y)$. George~P. Jelliss raised several interesting questions about these graphs, and established some of their fundamental properties. The purpose of this paper is to characterize when the graphs are connected, for arbitrary~$r$ and~$s$, and to determine the smallest boards with Hamiltonian circuits when $s=r+1$ or $r=1$. | |
| dc.identifier | https://arxiv.org/abs/math/9411240 | |
| dc.identifier | http://arxiv.org/abs/math/9411240 | |
| dc.identifier | Math. Gazette 78 (1994), 274--297 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/152945 | |
| dc.subject | Combinatorics | |
| dc.title | Leaper graphs | |
| dc.type | text |