Decomposing the cube into paths

DOI10.1016/J.DISC.2014.07.019zbMATH Open1300.05250arXiv1310.6776OpenAlexW2068532908MaRDI QIDQ740656FDOQ740656

Authors: Joshua Erde 

Publication date: 4 September 2014

Published in: Discrete Mathematics (Search for Journal in Brave)

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.

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

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

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)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Star decompositions of cubes
• Decomposing the hypercube \(Q_n\) into \(n\) isomorphic edge-disjoint trees
• On the decomposition of n‐cubes into isomorphic trees
• Edge decompositions of hypercubes by paths and by cycles
• Edge decompositions of hypercubes by paths

Cited In (14)

• Decomposition of hypercubes into sunlet graphs of order eight
• Title not available (Why is that?)
• Decomposing complete graphs into cubes
• Title not available (Why is that?)
• Decomposing 8-regular graphs into paths of length 4
• Long path and cycle decompositions of even hypercubes
• Partitioning the vertices of a torus into isomorphic subgraphs
• Decomposing 10-regular graphs into paths of length 5
• Decomposition of hypercubes into regular connected bipancyclic subgraphs
• Edge decompositions of hypercubes by paths
• Dissecting Cuboids into Cuboids
• Path bundles on \(n\)-cubes
• Decomposing regular graphs with prescribed girth into paths of given length
• Sphere decompositions of hypercubes

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)