# Long path and cycle decompositions of even hypercubes

Axenovich, Maria 1; Offner, David; Tompkins, Casey
1 Karlsruher Institut für Technologie (KIT)

##### Abstract:
We consider edge decompositions of the n-dimensional hypercube Q$_{n}$ into isomorphic copies of a given graph H. While a number of results are known about decomposing Q$_{n}$ into graphs from various classes, the simplest cases of paths and cycles of a given length are far from being understood. A conjecture of Erde asserts that if n is even, ℓ < 2$^{2}$ and ℓ divides the number of edges of Q$_{n}$, then the path of length ℓ decomposes Q$_{n}$. Tapadia et al. proved that any path of length 2$^{m}$n, where 2$^{m}$ < n, satisfying these conditions decomposes Q$_{n}$. Here, we make progress toward resolving Erde’s conjecture by showing that cycles of certain lengths up to 2$^{n+1}$/n decompose Q$_{n}$. As a consequence, we 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.

 Zugehörige Institution(en) am KIT Institut für Algebra und Geometrie (IAG) Publikationstyp Zeitschriftenaufsatz Publikationsmonat/-jahr 06.2021 Sprache Englisch Identifikator ISSN: 0195-6698 KITopen-ID: 1000135034 Erschienen in European journal of combinatorics Verlag Academic Press Band 95 Seiten Art. Nr.: 103320 Nachgewiesen in Web of ScienceScopusDimensions
KIT – Die Forschungsuniversität in der Helmholtz-Gemeinschaft
KITopen Landing Page