Optimal cycles enclosing all the nodes of a $k$-dimensional hypercube

Abstract

We solve the general problem of visiting all the $2^k$ nodes of a $k$-dimensional hypercube by using a polygonal chain that has minimum link-length, and we show that this optimal value is given by $h(2,k):=3\cdot 2^{k-2}$ if and only if $k\in \mathbb{N}-\{0,1\}$. Furthermore, for any $k$ above one, we constructively prove that it is possible to visit once and only once all the aforementioned nodes, $H(2,k):=\{\{0,1\}\times \{0,1\}\times \cdots \times \{0,1\}\}\subset {\mathbb{R}}^k$, with a cycle (i.e., a closed path) having only $3\cdot 2^{k-2}$ links.

arXiv comment13 pages, 5 figures. Typos corrected; misprint in Section 3 fixed