On embedding Hamiltonian cycles in crossed cubes

Research output: Contribution to journalArticlepeer-review

37 Scopus citations


We study the embedding of Hamiltonian cycle in the Crossed Cube, a prominent variant of the classical hypercube, which is obtained by crossing some straight links of a hypercube, and has been attracting much research interest in literatures since its proposal. We will show that due to the loss of link-topology regularity, generating Hamiltonian cycles in a crossed cube is a more complicated procedure than in its original counterpart. The paper studies how the crossed links affect an otherwise succinct process to generate a host of well-structured Hamiltonian cycles traversing all nodes. The condition for generating these Hamiltonian cycles in a crossed cube is proposed. An algorithm is presented that works out a Hamiltonian cycle for a given link permutation. The useful properties revealed and algorithm proposed in this paper can find their way when system designers evaluate a candidate network' s competence and suitability, balancing regularity and other performance criteria, in choosing an interconnection network.

Original languageEnglish
Pages (from-to)334-346
Number of pages13
JournalIEEE Transactions on Parallel and Distributed Systems
Issue number3
StatePublished - Mar 2008


  • Crossed cube
  • Embedding
  • Hamiltonian cycles
  • Interconnection architectures
  • Network topology


Dive into the research topics of 'On embedding Hamiltonian cycles in crossed cubes'. Together they form a unique fingerprint.

Cite this