Embedding hypercubes into torus and Cartesian product of paths and cycles for minimizing wirelength

2023/02/26 by Tang, Zhiyi
#Combinatorics (math.CO) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics

paper · doi:10.48550/arxiv.2302.13237

Abstract

Though embedding problems have been considered for several regular graphs, it is still an open problem for hypercube into torus. In the paper, we prove the conjecture mathematically and obtain the minimum wirelength of embedding for hypercube into Cartesian product of paths and/or cycles. In addition, we explain that Gray code embedding is an optimal strategy in such embedding problems.

Related

• Embedding complete multi-partite graphs into Cartesian product of paths and cycles
• Embedding of Hypercube into Cylinder
• Optimal cycles enclosing all the nodes of a k-dimensional hypercube
• Embedding onto Wheel-like Networks
• Cycles and Paths Embedded in Varietal Hypercubes