Long path and cycle decompositions of even hypercubes (Q2033926)

Let \(G\) be a graph with vertex set \(V(G)\) and edge set \(E(G)\). The \(n\)-dimensional hypercube \(Q_n\) is the graph with \(V(Q_n)=\{0,1\}^{n}\) and edges between pairs of vertices that differ in exactly one coordinate. For two graphs \(G\) and \(H\), if \(G\) is a pairwise edge-disjoint union of isomorphic copies of \(H\), then we call that \(H\) decomposes \(G\). A conjecture of \textit{J. Erde} [Discrete Math. 336, 41--45 (2014; Zbl 1300.05250)] asserts that if \(n\) is even, \(l<2^{n}\) and \(l\) divides the number of edges of \(Q_n\), then the path of length \(l\) decomposes \(Q_n\). In this paper, the authors deal with edge decompositions of the \(n\)-dimensional hypercube \(Q_n\) into isomorphic copies of a given graph \(H\), and partly resolve Erde's conjecture by showing that cycles of certain lengths up to \(2^{n+1}/n\) decompose \(Q_n\). As a consequence, the authors show that \(Q_n\) can be decomposed into copies of any path of length at most \(2^{n}/n\) dividing the number of edges of \(Q_n\), thereby settling Erde's conjecture up to a linear factor.