Mutually independent Hamiltonian cycles in dual-cubes

Yuan-Kang Shih, Hui-Chun Chuang, Shin-Shin Kao, Jiann-Mean Tan

Research output: Contribution to journalArticlepeer-review

11 Scopus citations


The hypercube family Q(n) is one of the most well-known interconnection networks in parallel computers. With Q(n) , dual-cube networks, denoted by DCn , was introduced and shown to be a (n+1)-regular, vertex symmetric graph with some fault-tolerant Hamiltonian properties. In addition, DCn's are shown to be superior to Q(n)'s in many aspects. In this article, we will prove that the n-dimensional dual-cube DCn contains n+1 mutually independent Hamiltonian cycles for n >= 2. More specifically, let upsilon(i) is an element of V(DC (n) ) for 0 <= i <= |V(DCn)|-1 and let (upsilon(0,) upsilon(1,.....,) upsilon broken vertical bar v(DCn)broken vertical bar-1, upsilon(0)) be a Hamiltonian cycle of DCn . We prove that DCn contains n+1 Hamiltonian cycles of the form (upsilon(0,) upsilon(k)(1), .....,upsilon(k)vertical bar v (DCn)vertical bar-1, upsilon(0)) for 0 <= k <= n, in which v(i)(k) not equal v(i)(k') whenever k not equal k'. The result is optimal since each vertex of DCn has only n+1 neighbors.
Original languageEnglish
Pages (from-to)239-251
Number of pages13
JournalJournal of Supercomputing
Issue number2
StatePublished - Sep 2010


  • Hypercube; Dual-cube; Hamiltonian cycle; Hamiltonian connected; Mutually independent

Fingerprint Dive into the research topics of 'Mutually independent Hamiltonian cycles in dual-cubes'. Together they form a unique fingerprint.

Cite this