Hamiltonian cycles passing through matchings in k-ary n-cubes

2024/11/29 by Fan Wang, Liao, Baolai, Wang, Fan
Computer Science · Mathematics · Engineering · #Advanced Graph Theory Research #Limits and Structures in Graph Theory #graph theory and CDMA systems

paper · pdf · doi:10.48550/arxiv.2411.19482

Abstract

As we all know, the k-ary n-cube is a highly efficient interconnect network topology structure. It is also a concept of great significance, with a broad range of applications spanning both mathematics and computer science. In this paper, we study the existence of Hamiltonian cycles passing through prescribed matchings in k-ary n-cubes, and obtain the following result. For n≥5 and k≥4, every matching with at most 4n-20 edges is contained in a Hamiltonian cycle in the k-ary n-cube.

Related

• Prescribed matchings extend to Hamiltonian cycles in hypercubes with faulty edges
• Matchings in Hypercubes Extend to Long Cycles
• Matchings in hypercubes extend to long cycles
• A perfect matching reciprocity method for embedding multiple hypercubes in an augmented cube: Applications to Hamiltonian decomposition and fault-tolerant Hamiltonicity
• Constructing Two Edge-Disjoint Hamiltonian Cycles and Two Equal Node-Disjoint Cycles in Twisted Cubes