Divisibility of hypercubes by paths and cycles of prescribed length, and fundamental decompositions (the Mollard–Ramras questions)

The $n$-dimensional hypercube $Q_n$ has $n\cdot 2^{n-1}$ edges, so a decomposition of $Q_n$ into paths $P_k$ or cycles $C_k$ of $k$ edges each requires $k$ to divide $n\cdot 2^{n-1}$ (and, for cycles, $k$ to be even, since $Q_n$ is bipartite, and $n$ to be even, since every vertex has degree $n$ while each cycle through a vertex uses exactly two of its edges). Mollard and Ramras asked three questions: (1) for which divisors $k$ of $n\cdot 2^{n-1}$ does $P_k$ divide $Q_n$; (2) for which such $k$ does $C_k$ divide $Q_n$; and (3) when a decomposition exists, can its copies always be chosen as translates of one copy under a subgroup of the automorphism group of $Q_n$ (a fundamental set)? The path question is now fully resolved for odd $n$ ($P_k$ divides $Q_n$ if and only if $k\le n$ and $k\mid n\cdot 2^{n-1}$; Anick–Ramras, Erde), and for even $n$ it is settled for all $k\le 2^n/n$ (Axenovich–Offner–Tompkins), leaving Erde's conjecture for even $n$ in the range $2^n/n<k<2^n$. The cycle question and the fundamental-set question remain open in general. This problem asks for the complete characterization of path and cycle divisibility of hypercubes and for the fundamental-set realizations.

Background

The $n$-dimensional hypercube (or $n$-cube) $Q_n$ is the graph whose vertices are the $2^n$ binary strings of length $n$, with an edge between two strings that differ in exactly one coordinate; it has $2^{n-1}$ vertices per bipartition class and $n\cdot 2^{n-1}$ edges. A graph $H$ divides $G$ if the edge set of $G$ can be partitioned into the edge sets of edge-disjoint copies of $H$; here $P_k$ denotes the path with $k$ edges and $C_k$ the cycle with $k$ edges. Decomposing cubes into isomorphic subgraphs goes back to Kirkman and Ringel; classical results include the decomposition of $Q_n$ into Hamiltonian cycles for even $n\ge 2$, Fink's theorem on decomposing cubes into isomorphic trees, and Horak, Širáň and Wallis's study of decomposing cubes. Necessary conditions for $P_k$ or $C_k$ to divide $Q_n$ are: $k$ divides the edge count $n\cdot 2^{n-1}$; for cycles, $k$ is even (since $Q_n$ is bipartite, all its cycles are even) and $n$ is even (when $n$ is odd every vertex of $Q_n$ has odd degree $n$, while each cycle through a vertex uses exactly two of its incident edges, so no $C_k$ divides $Q_n$ for odd $n$); and $k\le 2^n$ for cycles, $k<2^n$ for paths (a copy cannot have more vertices than the cube). For odd $n$ there is a further restriction for paths: when $n$ is odd each vertex of $Q_n$ must be the endpoint of some path of the decomposition, forcing $k\le n$. Mollard and Ramras, continuing Ramras's earlier work on symmetric edge-decompositions of hypercubes, introduced the automorphism group $\mathrm{Aut}(Q_n)\cong \mathbb{Z}_2^n\rtimes S_n$ (coordinate flips and permutations) into the picture: a set of copies of $H$ partitioning $E(Q_n)$ is called fundamental if the copies are the translates of one fixed copy under a subgroup of $\mathrm{Aut}(Q_n)$, i.e. the decomposition is highly symmetric. They proved a number of partial cases — e.g. any tree with $k$ edges divides $Q_n$ whenever $k\mid n$; $P_{2k}$ divides $Q_n$ when $k\mid n$ and $k<n$; $P_4$ divides $Q_n$ for all $n\ge 4$; $C_{2n}$ admits a fundamental decomposition of $Q_n$ for even $n$; and $Q_n$ has a fundamental Hamiltonian cycle when $n$ is a power of $2$ — and posed the three questions above, noting that most cases were unresolved. Later work transformed the landscape for paths: Anick and Ramras proved for odd $n<2^{32}$ (and conjectured in general) that $P_k$ divides $Q_n$ exactly when $k\le n$ and $k\mid n\cdot 2^{n-1}$; Erde proved the conjecture for all odd $n$ and, for even $n$, conjectured that $P_k$ divides $Q_n$ whenever $k\mid n\cdot 2^{n-1}$ and $k<2^n$. Axenovich, Offner and Tompkins confirmed Erde's even-$n$ conjecture for all $k\le 2^n/n$ via new cycle decompositions of even-dimensional cubes into cycles of length $y\cdot 2^m$ ($y$ an odd divisor of $n$) of all such lengths at most $2^{n+1}/n$, and Tapadia, Waphare and Borse had earlier handled cycle lengths $2^m n$ with $2^m\le n$; Gibson and Offner covered all power-of-two cycle lengths $2^i$, $2\le i\le n$, for even $n$. Martinez-Perez gave explicit constructions covering 'virtually all' cycle lengths for cubes $Q_{2an}$ with $a\ge 3$ odd, and Aberle, Gold, Moshe and Offner developed the torus building block ($C_m\square C_n$ decompositions) that these inductive arguments rest on. Despite this progress, no complete characterization of the pairs $(n,k)$ for which $C_k$ divides $Q_n$ is known — Axenovich, Offner and Tompkins state explicitly that the cycle lengths between $2^{n+1}/n$ and $2^n$ remain open, giving $C_{7\cdot 2^{11}}$ in $Q_{14}$ as an example their methods cannot reach — and the fundamental-set question has advanced little beyond Mollard and Ramras's original special cases.

Problem Statement

Determine, completely, for every dimension $n$ and every integer $k$: (1) whether the path $P_k$ divides the $n$-dimensional hypercube $Q_n$; (2) whether the cycle $C_k$ divides $Q_n$; and (3) when a decomposition exists, whether it can be chosen so that its copies form a fundamental set, i.e. the translates of a single copy under a subgroup of $\mathrm{Aut}(Q_n)\cong\mathbb{Z}_2^n\rtimes S_n$. The three parts share one scientific objective: a structural characterization of path- and cycle-divisibility of hypercubes, together with the sharpest symmetry (fundamental realization) such decompositions can have. Concretely, the target is a necessary and sufficient characterization of the pairs $(n,k)$ for which $P_k$- and $C_k$-decompositions of $Q_n$ exist (necessarily $k\mid n\cdot 2^{n-1}$; additionally $n$ even, $k$ even and $k\le 2^n$ for cycles, and $k<2^n$ for paths; for paths with $n$ odd the complete answer is known — $P_k$ divides $Q_n$ exactly when $k\le n$ and $k\mid n\cdot 2^{n-1}$ — while for paths with $n$ even the conjectured answer is that $P_k$ divides $Q_n$ for exactly those $k$ with $k\mid n\cdot 2^{n-1}$ and $k<2^n$; this is Erde's conjecture, proved so far only for $k\le 2^n/n$), together with a determination, for each admitting $k$, of whether a fundamental decomposition exists. Touchstone open instances include decompositions of $Q_6$ into paths of length $48$, decompositions of $Q_{14}$ into cycles of length $7\cdot 2^{11}$, and fundamental-set decompositions beyond the known special cases.

References

1. Michel Mollard and Mark Ramras (2014). Edge Decompositions of Hypercubes by Paths and by Cycles. Graphs and Combinatorics 31(3):729–741. DOI: 10.1007/s00373-013-1402-0, https://doi.org/10.1007/s00373-013-1402-0 (preprint: arXiv:1205.4161, https://arxiv.org/abs/1205.4161)
2. David Anick and Mark Ramras (2013). Edge Decompositions of Hypercubes by Paths. arXiv:1308.4949, https://arxiv.org/abs/1308.4949
3. Joshua Erde (2014). Decomposing the cube into paths. Discrete Mathematics 336:41–45. DOI: 10.1016/j.disc.2014.07.019, https://doi.org/10.1016/j.disc.2014.07.019 (preprint: arXiv:1310.6776, https://arxiv.org/abs/1310.6776)
4. S. A. Tapadia, B. N. Waphare, and Y. M. Borse (2018). Decompositions of $n$-Cube into $2^mn$-Cycles. arXiv:1804.01243, https://arxiv.org/abs/1804.01243
5. Maria Axenovich, David Offner, and Casey Tompkins (2021). Long path and cycle decompositions of even hypercubes. European Journal of Combinatorics 95:103320. DOI: 10.1016/j.ejc.2021.103320, https://doi.org/10.1016/j.ejc.2021.103320 (preprint: arXiv:1905.10114, https://arxiv.org/abs/1905.10114)
6. Samuel Gibson and David Offner (2024). Decompositions of even hypercubes into cycles whose length is a power of 2. Involve, a Journal of Mathematics 17(2):233–247. DOI: 10.2140/involve.2024.17.233, https://doi.org/10.2140/involve.2024.17.233 (preprint: arXiv:2107.07450, https://arxiv.org/abs/2107.07450; the preprint title reads 'a power of two')
7. Idael Martinez-Perez (2024). Generalization of Cycle Decompositions of Even Dimensional Hypercubes on $d$-Dimensional Toruses. arXiv:2403.03885, https://arxiv.org/abs/2403.03885
8. Moriah Aberle, Sarah Gold, Rivkah Moshe, and David Offner (2025). Cycle Decompositions of Cartesian Products of Two Cycles. Graphs and Combinatorics 41(4). DOI: 10.1007/s00373-025-02953-2, https://doi.org/10.1007/s00373-025-02953-2
9. P. Horak, J. Širáň, and W. Wallis (1996). Decomposing cubes. Journal of the Australian Mathematical Society, Series A 61:119–128. DOI: 10.1017/S1446788700000112, https://doi.org/10.1017/S1446788700000112
10. Mark Ramras (1991). Symmetric edge-decompositions of hypercubes. Graphs and Combinatorics 7:65–87. DOI: 10.1007/BF01789464, https://doi.org/10.1007/BF01789464
11. D. Saranya, S. Jeevadoss, V. Nalini, and V. Chitra (2025). Decomposition of hypercube graphs into paths and cycles having $k$ edges. AKCE International Journal of Graphs and Combinatorics 22(2):190–195. DOI: 10.1080/09728600.2024.2444564, https://doi.org/10.1080/09728600.2024.2444564
12. Farid Bouya, Ebadollah S. Mahmoodian, Modjtaba Shokrian Zini, and Mojtaba Tefagh (2020). A Highly Symmetric Hamilton Decomposition for Hypercubes. arXiv:2004.02750, https://arxiv.org/abs/2004.02750