### Abstract

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 language | English |
---|---|

Pages (from-to) | 239-251 |

Number of pages | 13 |

Journal | Journal of Supercomputing |

Volume | 54 |

Issue number | 2 |

DOIs | |

State | Published - Sep 2010 |

### Keywords

- 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

Shih, Y-K., Chuang, H-C., Kao, S-S., & Tan, J-M. (2010). Mutually independent Hamiltonian cycles in dual-cubes.

*Journal of Supercomputing*,*54*(2), 239-251. https://doi.org/10.1007/s11227-009-0317-2