Optimal cycles enclosing all the nodes of a $k$-dimensional hypercube
Fuente:
arXiv
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2022
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866913190561972224 |
|---|---|
| author | Rinaldi, Roberto Ripà, Marco |
| author_facet | Rinaldi, Roberto Ripà, Marco |
| contents | 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 \dots \times \{0,1\}\} \subset \mathbb{R}^k$, with a cycle (i.e., a closed path) having only $3 \cdot 2^{k-2}$ links. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2212_11216 |
| institution | arXiv |
| publishDate | 2022 |
| record_format | arxiv |
| spellingShingle | Optimal cycles enclosing all the nodes of a $k$-dimensional hypercube Rinaldi, Roberto Ripà, Marco Combinatorics 05C38 (Primary) 05C12, 91A43 (Secondary) 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 \dots \times \{0,1\}\} \subset \mathbb{R}^k$, with a cycle (i.e., a closed path) having only $3 \cdot 2^{k-2}$ links. |
| title | Optimal cycles enclosing all the nodes of a $k$-dimensional hypercube |
| topic | Combinatorics 05C38 (Primary) 05C12, 91A43 (Secondary) |
| url | https://arxiv.org/abs/2212.11216 |