Decomposing the cube into paths

DOI10.1016/J.DISC.2014.07.019MaRDI QIDQ740656zbMATH OpenOpenAlexFDO

Authors Joshua Erde

Publication date 4 September 2014

Published in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1310.6776

zbMATH Keywords

hypercubegraph decomposition

Mathematics Subject Classification ID

Paths and cycles (05C38) Hypergraphs (05C65) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Abstract: We consider the question of when the $n$-dimensional hypercube can be decomposed into paths of length $k$. Mollard and Ramras cite{MR2013} noted that for odd $n$ it is necessary that $k$ divides $n{2}^{n-1}$ and that $kleqn$. Later, Anick and Ramras cite{AR2013} showed that these two conditions are also sufficient for odd $nleq{2}^{32}$ and conjectured that this was true for all odd $n$. In this note we prove the conjecture.

Recommendations

• Long path and cycle decompositions of even hypercubes
• Publication:3204492
• Disjoint paths in hypercubes with prescribed origins and lengths
• Edge decompositions of hypercubes by paths
• Path coverings with prescribed ends of the \(n\)-dimensional binary hypercube

Cites work

• scientific article; zbMATH DE number 4173021 (Why is no real title available?)
• scientific article; zbMATH DE number 52113 (Why is no real title available?)
• Decomposing the hypercube \(Q_n\) into \(n\) isomorphic edge-disjoint trees
• Edge decompositions of hypercubes by paths
• Edge decompositions of hypercubes by paths and by cycles
• On the decomposition of n‐cubes into isomorphic trees
• Star decompositions of cubes

Cited in

(14)

• Decomposing 8-regular graphs into paths of length 4
• Decomposition of hypercubes into sunlet graphs of order eight
• Decomposing 10-regular graphs into paths of length 5
• Long path and cycle decompositions of even hypercubes
• scientific article; zbMATH DE number 4181376 (Why is no real title available?)
• Decomposition of hypercubes into regular connected bipancyclic subgraphs
• Partitioning the vertices of a torus into isomorphic subgraphs
• Dissecting Cuboids into Cuboids
• Decomposing regular graphs with prescribed girth into paths of given length
• Edge decompositions of hypercubes by paths
• scientific article; zbMATH DE number 1026076 (Why is no real title available?)
• Path bundles on \(n\)-cubes
• Sphere decompositions of hypercubes
• Decomposing complete graphs into cubes

This page was built for publication: Decomposing the cube into paths

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q740656)