A Highly Symmetric Hamilton Decomposition for Hypercubes

2020/04/06 by Bouya, Farid, Mahmoodian, Ebadollah S., Zini, Modjtaba Shokrian +1
#Combinatorics (math.CO) #FOS: Mathematics

paper · doi:10.48550/arxiv.2004.02750

Abstract

A Hamilton decomposition of a graph is a partitioning of its edge set into disjoint spanning cycles. The existence of such decompositions is known for all hypercubes of even dimension 2n. We give a decomposition for the case n = 2^a3^b that is highly symmetric in the sense that every cycle can be derived from every other cycle just by permuting the axes. We conjecture that a similar decomposition exists for every n.

Related

• The Hamilton compression of highly symmetric graphs
• The number of Hamiltonian decompositions of regular graphs
• Counting Hamilton decompositions of oriented graphs
• Long path and cycle decompositions of even hypercubes
• Symmetric property and edge-disjoint Hamiltonian cycles of the spined cube