Decomposing the cube into paths

2013/10/24 by Joshua Erde, Erde, Joshua
Computer Science · Engineering · Mathematics · #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics #Interconnection Networks and Systems #VLSI and FPGA Design Techniques #math.CO

paper · pdf · doi:10.48550/arxiv.1310.6776

7 pages, 2 figures

arxiv created 2013/10/24 · openalex publication_date 2013/10/24 · arxiv updated 2013/10/28 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

We consider the question of when the n-dimensional hypercube can be decomposed into paths of length k. Mollard and Ramras \citeMR2013 noted that for odd n it is necessary that k divides n2^n-1 and that k≤ n. Later, Anick and Ramras \citeAR2013 showed that these two conditions are also sufficient for odd n ≤ 2³² and conjectured that this was true for all odd n. In this note we prove the conjecture.

Related

• Long path and cycle decompositions of even hypercubes
• Edge Decompositions of Hypercubes by Paths
• Decompositions of n-Cube into 2^mn-Cycles
• Partitioning the hypercube into smaller hypercubes
• Decomposition of a cube into nearly equal smaller cubes