Mutually independent Hamiltonian cycles in k-ary n-cubes when k is even

The k-ary n-cube has been used as the underlying topology for many practical multicomputers, and has been extensively studied in the past. In this article, we will prove that any k-ary n  -cube Qnk, where n⩾2n⩾2 is an integer and k⩾4k⩾4 is an even integer, contains 2n   mutually independent Hamiltonian cycles. More specifically, let N=|V(Qnk)|,v(i)∈V(Qnk) for 1⩽i⩽N1⩽i⩽N, and 〈v(1),v(2),…,v(N),v(1)〉 be a Hamiltonian cycle of Qnk. We prove that Qnk contains 2n   Hamiltonian cycles, denoted by Cl=〈v(1),vl(2)…,vl(N),v(1)〉 for all 0⩽l⩽2n-10⩽l⩽2n-1, such that vl(i)≠vl′(i)vl(i)≠vl′(i) for all 2⩽i⩽N2⩽i⩽N whenever l≠l′l≠l′. The result is optimal since each vertex of Qnk has exactly 2n neighbors.

It is known that Q24 contains 4 Hamiltonian cycles whose internal vertices never collide. We prove that Qnk contains 2n   Hamiltonian cycles whose internal vertices never collide for any even integer k⩾4k⩾4.Figure optionsDownload as PowerPoint slideResearch highlights
► For any integer n and any even integer k⩾4, we prove the existence of 2n mutually independent Hamiltonian cycles in the k-ary n  -cube, Qnk.
► The construction scheme is given concretely for general cases, and a specific example is presented as well.
► The result is optimal in the sense that the number of mutually independent Hamiltonian cycles constructed in Qnk is maximum since each vertex of Qnk has exactly 2n neighbors.