Long path and cycle decompositions of even hypercubes

2019/05/24 by Axenovich, Maria, Offner, David, Tompkins, Casey
#Combinatorics (math.CO) #FOS: Mathematics

paper · doi:10.48550/arxiv.1905.10114

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ⁿ 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^mn, where 2^m

Related

• Edge Decompositions of Hypercubes by Paths
• Decomposing the cube into paths
• Decompositions of n-Cube into 2^mn-Cycles
• Generalization of Cycle Decompositions of Even Dimensional Hypercubes on d-Dimensional Toruses
• Edge Decompositions of Hypercubes by Paths and by Cycles