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

2022/12/17 by Rinaldi, Roberto, Ripà, Marco
#05C38 (Primary) 05C12 #91A43 (Secondary) #Combinatorics (math.CO) #FOS: Mathematics

paper · doi:10.48550/arxiv.2212.11216

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 ⋅ 2^k-2 if and only if k ∈ ℕ-\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\ × \0,1\ × … × \0,1\\ ⊂ ℝ^k, with a cycle (i.e., a closed path) having only 3 ⋅ 2^k-2 links.

Related

• Minimum-Link Covering Trails for any Hypercubic Lattice
• Cycles and Paths Embedded in Varietal Hypercubes
• Shortest polygonal chains covering each planar square grid
• Embedding multidimensional grids into optimal hypercubes
• Embedding hypercubes into torus and Cartesian product of paths and cycles for minimizing wirelength