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\}\) .

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

Embedding K Edge-Disjoint Hamiltonian Cycles on Folded Hypercubes

  • Kung-Jui Pai

摘要

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\}\) .