Path and cycle decompositions of the hypercube: the divisibility characterization (Erde's conjecture) and fundamental-set realization of Ramras

For the n-dimensional hypercube graph $Q_n$, which has $2^n$ vertices and $n2^{n-1}$ edges, Mollard and Ramras asked for which $k$ dividing $n2^{n-1}$ the path with $k$ edges and the cycle with $k$ edges edge-decompose $Q_n$, and which decomposing edge sets can be realized as fundamental sets, i.e. as a single copy whose translates under a subgroup of the automorphism group of $Q_n$ partition the edge set. For odd $n$ the path question is completely settled (a path decomposition exists if and only if $k \le n$ and $k$ divides $n2^{n-1}$), and for even $n$ all lengths up to $2^n/n$ are settled, but Erde's conjecture — that for even $n$ every admissible length $k < 2^n$ decomposes $Q_n$ — remains open for lengths between $2^n/n$ and $2^n$, the analogous cycle-length characterization is open for intermediate and long lengths, and Ramras's conjecture that for every even $n \ge 4$ the edge set of a path of length $2n$ is a fundamental set for $Q_n$ is only partially solved. The problem is posed at the sources' natural generality over all $n$ and $k$.

Background

The $n$-dimensional hypercube (or $n$-cube) $Q_n$ is the graph whose vertices are the $2^n$ binary strings of length $n$, two vertices being adjacent when they differ in exactly one coordinate; it is $n$-regular with $n2^{n-1}$ edges and is the standard model of interconnection networks. A graph $H$ decomposes (or divides) a graph $G$ when $E(G)$ is a disjoint union of edge sets of copies of $H$; throughout, a $k$-path $P_k$ and a $k$-cycle $C_k$ are the path and the cycle with exactly $k$ edges. Decomposing $Q_n$ into isomorphic copies of a fixed small graph $H$ is the hypercube analogue of the classical graph-decomposition problem solved for complete graphs by Wilson's theorem, and paths and cycles are the simplest choices of $H$ — yet, as Axenovich, Offner, and Tompkins put it, these simplest cases are far from understood. The obvious necessary conditions for $P_k$ to divide $Q_n$ are $k \mid n2^{n-1}$ and $k \le 2^n - 1$ (a path with $k$ edges spans $k+1$ distinct vertices); for $C_k$ one needs $k$ even, $4 \le k \le 2^n$, and $k \mid n2^{n-1}$; moreover $n$ itself must be even, since $Q_n$ is $n$-regular and a union of edge-disjoint cycles has even degree at every vertex.

The problem has a decades-long history. Ringel (1955) proved that $Q_n$ decomposes into Hamiltonian cycles (cycles through all $2^n$ vertices) when $n$ is a power of 2 and asked about all even $n$; the general even case follows from the Hamiltonian decomposition theorem of Aubert and Schneider for Cartesian products of cycles, since $Q_n$ for even $n$ is the Cartesian product of $n/2$ squares (a Cartesian product $G \square H$ joins two copies of the graphs by matching corresponding vertices with edges). Splitting the Hamiltonian cycles of such a decomposition into equal pieces immediately yields decompositions of $Q_n$ into $2^j$-paths and shows $Q_n$ for even $n$ decomposes into $2^j$-cycles, $2 \le j \le n$ (the cycle statement, in greater generality, is due to El-Zanati and Vanden Eynden). Fink proved that every tree with $k$ edges divides $Q_n$ whenever $k \mid n$, and Horak, Širáň, and Wallis proved that any graph with $n$ edges whose blocks (maximal 2-connected pieces) are even cycles or single edges divides $Q_n$. Mollard and Ramras, continuing Ramras's earlier work, proved among other results that $P_{2k}$ divides $Q_n$ whenever $k \mid n$ and $k < n$, that $P_{2^j}$ divides $Q_n$ for even $n$ and $j < n$, and that $P_4$ divides $Q_n$ for $n \ge 4$; they then asked the general question: for which $k$ dividing $n2^{n-1}$ does $P_k$ divide $Q_n$, and for which does $C_k$ divide $Q_n$?

For odd $n$ the path question has a complete answer. Every vertex of $Q_n$ then has odd degree, so every vertex must be an endpoint of some path in any path decomposition; counting endpoints shows each path has length at most $n$. Anick and Ramras (preprint) and, independently in print, Erde proved the converse: for odd $n$, every path of length $k \le n$ with $k \mid n2^{n-1}$ divides $Q_n$. For even $n$, Erde formulated the strong conjecture that divisibility is the only obstruction short of the trivial vertex-count bound: if $n$ is even, $k < 2^n$, and $k \mid n2^{n-1}$, then $P_k$ divides $Q_n$. Tapadia, Waphare, and Borse proved that a $2^m n$-cycle divides the even cube $Q_n$ whenever $2^m \le n$, which by cycle-splitting gives the path cases $k = n, 2n, \dots, 2^{m-1}n$; Axenovich, Offner, and Tompkins subsequently proved that for even $n$ every admissible length $k \le 2^n/n$ works, settling Erde's conjecture 'up to a linear factor', and constructed cycle decompositions of many long lengths of the form $y \cdot 2^m$ with $y$ an odd divisor of $n$. Saranya, Jeevadoss, Nalini, and Chitra characterized mixed decompositions into $k$-paths and $k$-cycles in the sub-regime $k \mid n$.

A second strand concerns symmetry of the decomposition. A subset $F$ of $E(Q_n)$ is a fundamental set for $Q_n$ (with respect to a subgroup $\mathcal{G}$ of the automorphism group $\mathrm{Aut}(Q_n)$, whose $2^n \cdot n!$ elements are each uniquely a coordinate-complementing reflection composed with a coordinate permutation) if the translates $\{g(F) : g \in \mathcal{G}\}$ form an edge decomposition of $Q_n$ — that is, the entire decomposition is the orbit of a single copy under a group of symmetries of the cube. Ramras, who introduced this notion, proved that certain $n$-cycles of $Q_n$ are fundamental and conjectured (1997) that for every even $n \ge 4$ the edge set of a path of length $2n$ is a fundamental set for $Q_n$; Mollard and Ramras proved the analogous statement for a particular $2n$-cycle and showed that a subcube $Q_k$ is fundamental for $Q_n$ if and only if $k \mid n$. Tapadia, Waphare, and Borse obtained a partial solution of Ramras's path conjecture via their cycle decompositions, but the conjecture remains open in general, as does the broader question of which dividing paths and cycles can be realized as fundamental sets.

Problem Statement

Determine exactly which paths and cycles edge-decompose the hypercube, and which of these decompositions can be made fundamental. Concretely, with $Q_n$ the $n$-dimensional hypercube ($2^n$ vertices, $n2^{n-1}$ edges), a $k$-path and a $k$-cycle having $k$ edges:

1. (Even-dimensional path characterization; Erde's conjecture.) For even $n$, is it true that $P_k$ divides $Q_n$ for every $k$ with $k \mid n2^{n-1}$ and $k < 2^n$? Equivalently: complete the characterization for the open range $2^n/n < k < 2^n$; all $k \le 2^n/n$ are already settled, and the range $k > 2^{n-1}$ is not reachable by splitting cycle decompositions.
2. (Cycle-length characterization.) For each $n \ge 2$ (for odd $n$ the answer is empty: $Q_n$ is $n$-regular and a union of edge-disjoint cycles has even degree at every vertex, so the question is substantive precisely for even $n$), determine the set of even $k$ with $4 \le k \le 2^n$ and $k \mid n2^{n-1}$ such that $C_k$ divides $Q_n$. Known families include $k = n, 2n$ (even $n$), $k = 2^j$ ($2 \le j \le n$), $k = 2^m n$ ($2^m \le n$), and the long lengths of the form $y \cdot 2^m$ ($y$ an odd divisor of $n$) constructed by Axenovich–Offner–Tompkins; the longest lengths remain uncharacterized: it is open which cycles of lengths between $2^{n+1}/n$ and $2^n$ decompose $Q_n$ (e.g. it is open whether $C_{7 \cdot 2^{11}}$ divides $Q_{14}$).
3. (Fundamental-set realization.) A set $F \subseteq E(Q_n)$ is a fundamental set for $Q_n$ if for some subgroup $\mathcal{G} \le \mathrm{Aut}(Q_n)$ the translates $\{g(F) : g \in \mathcal{G}\}$ partition $E(Q_n)$. Determine for which admissible $k$ a $k$-path or $k$-cycle can be fundamental for $Q_n$; in particular, resolve Ramras's conjecture (1997): for every even $n \ge 4$, the edge set of a path of length $2n$ is a fundamental set for $Q_n$ (currently only partially solved).

The problem is stated at the sources' natural generality (all $n$ and all admissible $k$); no finite-size, divisibility, or method restriction is intended. For odd $n$ the path question is already completely answered ($P_k$ divides $Q_n$ if and only if $k \le n$ and $k \mid n2^{n-1}$), so new information there concerns only the cycle and fundamental-set parts.

References

1. Michel Mollard and Mark Ramras, 'Edge decompositions of hypercubes by paths and by cycles', Graphs and Combinatorics 31 (2015) 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. Joshua Erde, 'Decomposing the cube into paths', Discrete Mathematics 336 (2014) 41–45. DOI 10.1016/j.disc.2014.07.019, https://doi.org/10.1016/j.disc.2014.07.019
3. S. A. Tapadia, B. N. Waphare and Y. M. Borse, 'Decompositions of $n$-Cube into $2^m n$-Cycles', arXiv:1804.01243 (2018). https://arxiv.org/abs/1804.01243
4. Maria Axenovich, David Offner and Casey Tompkins, 'Long path and cycle decompositions of even hypercubes', European Journal of Combinatorics 95 (2021) article 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)
5. Mark Ramras, 'Fundamental subsets of edges of hypercubes', Ars Combinatoria 46 (1997) 3–24. Zbl 0933.05068, https://zbmath.org/?q=an:0933.05068
6. Mark Ramras, 'Symmetric edge-decompositions of hypercubes', Graphs and Combinatorics 7 (1991) 65–87. DOI 10.1007/BF01789464, https://doi.org/10.1007/BF01789464
7. David Anick and Mark Ramras, 'Edge Decompositions of Hypercubes by Paths', arXiv:1308.4949 (2013). https://arxiv.org/abs/1308.4949
8. S. El-Zanati and C. Vanden Eynden, 'Cycle factorizations of cycle products', Discrete Mathematics 189 (1998) 267–275. DOI 10.1016/S0012-365X(98)00053-3, https://doi.org/10.1016/S0012-365X(98)00053-3
9. P. Horak, J. Širáň and W. Wallis, 'Decomposing cubes', Journal of the Australian Mathematical Society Series A 61 (1996) 119–128. DOI 10.1017/S1446788700000112, https://doi.org/10.1017/S1446788700000112
10. Jacques Aubert and Bernadette Schneider, 'Décomposition de la somme cartésienne d'un cycle et de l'union de deux cycles hamiltoniens en cycles hamiltoniens', Discrete Mathematics 38 (1982) 7–16. DOI 10.1016/0012-365X(82)90163-7, https://doi.org/10.1016/0012-365X(82)90163-7
11. John Frederick Fink, 'On the decomposition of n-cubes into isomorphic trees', Journal of Graph Theory 14 (1990) 405–411. DOI 10.1002/jgt.3190140403, https://doi.org/10.1002/jgt.3190140403
12. D. Saranya, S. Jeevadoss, V. Nalini and V. Chitra, 'Decomposition of hypercube graphs into paths and cycles having k edges', AKCE International Journal of Graphs and Combinatorics 22 (2025) 190–195. DOI 10.1080/09728600.2024.2444564, https://doi.org/10.1080/09728600.2024.2444564