On the existence of Hamiltonian cycles in hypercubes

Abstract

Building on the results of our previous work on Euclidean leaper tours, considering all integers $k>1$ and $h>0$, we study the existence of Hamiltonian cycles in the vertex set $C(2,k):=\{0,1{\}}^k$ of the $k$-dimensional hypercube when the Euclidean distance between consecutive vertices is fixed. Since the distance between two vertices of $C(2,k)$ is $\sqrt{h}$ for some integer $h$, the problem amounts to determining for which integers $k$ and $h$ there exists a Hamiltonian cycle whose associated Euclidean distance is $\sqrt{h}$. In this paper, we prove that such cycles exist if and only if $h$ is odd and $1\le h\le k-1$. As a result, for all integers $a\ge 0$, $b\ge a$ with $b>0$, we provide a necessary and sufficient condition for the existence of closed Euclidean $(a,b)$-leaper tours on $2\times 2\times \cdots \times 2$ chessboards, where the associated distance equals $\sqrt{a^2+b^2}$.

arXiv comment6 pages