Long path and cycle decompositions of even hypercubes

Abstract

©2021 The Author(s). Published by Elsevier Ltd. This is an open access article under the CC BY-NC-ND license (http://creativecommons.org/licenses/by-nc-nd/4.0/). 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, l < 2(n) and l divides the number of edges of Q(n), then the path of length l decomposes Q(n). Tapadia et al. proved that any path of length 2(m)n, where 2(m) < n, satisfying these conditions decomposes Q. Here, we make progress toward resolving Erde&apos;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&apos;s conjecture up to a linear factor. (C) 2021 The Author(s). Published by Elsevier Ltd.