Snake Paths in King and Knight Graphs

Abstract

A snake path in a graph $G$ is a path in $G$ which is also an induced subgraph of $G$. For all $n$, we find the greatest length of a snake path in the $n\times n$ king graph and we give a complete description of the paths which attain this greatest length. The even and odd cases behave very differently. We also estimate the greatest length of a snake path or cycle in the $m\times n$ knight graph, for all $m$ and $n$.

arXiv comment36 pages, 26 figures