KIT | KIT-Bibliothek | Impressum | Datenschutz

Long path and cycle decompositions of even hypercubes

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


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.

Verlagsausgabe §
DOI: 10.5445/IR/1000135034
Veröffentlicht am 06.07.2021
DOI: 10.1016/j.ejc.2021.103320
Zitationen: 1
Zitationen: 1
Cover der Publikation
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 Dimensions
Web of Science
KIT – Die Forschungsuniversität in der Helmholtz-Gemeinschaft
KITopen Landing Page