Edge Decompositions of Hypercubes by Paths

2013/08/22 by David J. Anick, David Anick, Anick, David +2
Computer Science · Engineering · Mathematics · #2010 05C51 #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics #Interconnection Networks and Systems #graph theory and CDMA systems #math.CO #msc:05C51 #msc:2010

paper · pdf · doi:10.48550/arxiv.1308.4949

arxiv created 2013/08/22 · openalex publication_date 2013/08/22 · arxiv updated 2013/08/23 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

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 ≃ H\. Our main result is that for q odd and q < 2³², the path of length m, P_m, divides Q_q if and only if m ≤ q and m | (q × 2^q-1).

Related

• Edge Decompositions of Hypercubes by Paths and by Cycles
• Long path and cycle decompositions of even hypercubes
• Decomposing the cube into paths
• Cycles and Paths Embedded in Varietal Hypercubes
• Decompositions of highly connected graphs into paths of length five