Edge decompositions of hypercubes by paths

MaRDI QIDQ5245542zbMATH OpenFDO

Authors David J. Anick, Mark Ramras

Publication date 9 April 2015

Full work available at URL https://arxiv.org/abs/1308.4949, http://ajc.maths.uq.edu.au//pdf/61/ajc_v61_p210.pdf

zbMATH Keywords

edge decompositions of graphs

Mathematics Subject Classification ID

Paths and cycles (05C38) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Abstract: Many authors have investigated edge decompositions of graphs by the edge sets of isomorphic copies of special subgraphs. For $q$- dimensional hypercubes $Q_q$ various researchers have done this for cer- tain trees, paths, and cycles. In this paper we shall say that "$H$ divides $G$" if $E(G)$ is the disjoint union of $fE(H_i)|H_{i}simeqH$. Our main result is that for $q$ odd and $q<2^{32}$, the path of length $m$, $P_m$, divides $Q_q$ if and only if $mleqq$ and $m|(qimes{2}^{q-1})$.

Recommendations

• Edge decompositions of hypercubes by paths and by cycles
• Long path and cycle decompositions of even hypercubes
• Decomposing complete graphs into cubes
• Decomposing the cube into paths
• Decomposition of hypercube graphs into paths and cycles of length four

Cited in

(12)

• Symmetric edge-decompositions of hypercubes
• Long path and cycle decompositions of even hypercubes
• Partitioning the vertices of a torus into isomorphic subgraphs
• Edge decompositions of hypercubes by paths and by cycles
• scientific article; zbMATH DE number 4181376 (Why is no real title available?)
• Decomposition of hypercube graphs into paths and cycles of length four
• Decomposing complete graphs into cubes
• Decomposition of hypercubes into sunlet graphs of order eight
• Multidecomposition of hypercube graphs into paths, cycles and stars
• Decomposition of hypercube graphs into paths and cycles having k edges
• Decomposition of hypercubes into sunlet graphs
• Decomposing the cube into paths

This page was built for publication: Edge decompositions of hypercubes by paths

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