Embedding K Edge-Disjoint Hamiltonian Cycles on Folded Hypercubes
摘要
The n-dimensional folded hypercube \(FQ_n\) is a well-known extension of the n-dimensional hypercube that can be constructed by adding an edge to every pair of vertices with complementary addresses. The existence of the Hamiltonian cycle provides advantages for implementing algorithms that require a ring structure. In addition, \(k (\ge 2)\) edge-disjoint Hamiltonian cycles also provide higher transmission efficiency for all-to-all communication algorithms and provide fault-tolerant routing for network transmission. This paper proves that there exist two edge-disjoint Hamiltonian cycles on \(FQ_n\) while \(n \ge 3\) ; and for k edge-disjoint Hamiltonian cycles on \(FQ_n\) , the maximum k is 2 while \(n \in \{3, 4\}\) and 3 while \(n \in \{5, 6\}\) .