On the existence of Hamiltonian cycles in hypercubes
Fuente:
arXiv
Guardado en:
| Autores principales: | , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2024
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866914411874091008 |
|---|---|
| author | Di Pietro, Gabriele Ripà, Marco |
| author_facet | Di Pietro, Gabriele Ripà, Marco |
| contents | 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 \leq h \leq k-1$. As a result, for all integers $a \geq 0$, $b \geq 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}$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2409_03073 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | On the existence of Hamiltonian cycles in hypercubes Di Pietro, Gabriele Ripà, Marco Combinatorics 05C12, 05C45 (Primary) 05C38 (Secondary) 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 \leq h \leq k-1$. As a result, for all integers $a \geq 0$, $b \geq 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}$. |
| title | On the existence of Hamiltonian cycles in hypercubes |
| topic | Combinatorics 05C12, 05C45 (Primary) 05C38 (Secondary) |
| url | https://arxiv.org/abs/2409.03073 |