Determination of Hamiltonian cycles in cube-based networks using generalized gray codes

Document Type



Gray Codes (GCs) are useful in finding the Hamiltonian path, embedding linear and mesh graphs, and identification of operational subcubes in a cube with some already allocated regions. We generalize the conventional GCs by allowing the successive codewords to have a Hamming distance of greater than one when necessary. This generalization provides a useful methodology for solving such problems as: embedding, subnetwork allocation and deallocation, and fault tolerant routing for non-standard cube-based networks. To demonstrate the usefulness of this GC characterization, we focus on the problem of ring (or linear array) embedding into viable alternatives of the n-cube, namely, folded hypercube, incomplete hypercube, twisted hypercube and multiply-twisted hypercube. We show the power of the link label representation in identifying the Hamiltonian paths (cycles) in the cube-based networks. Using the unified link label representation, Gray Codes are derived for the aforementioned networks. The available distinct GCs for each network are further enumerated. The GCs obtained as such render Hamiltonian cycles for each cube-based topology, thus providing embedding of rings (or linear arrays) of maximum size onto the cube. It is believed that the generalized GCs introduced here can be employed to solve many other problems in networks whose connectivity is defined by the binary labels of nodes.


Computer and Systems Architecture | Computer Engineering | Digital Communications and Networking | Electrical and Computer Engineering | VLSI and Circuits, Embedded and Hardware Systems


Use Find in Your Library, contact the author, or interlibrary loan to garner a copy of the item. Publisher policy does not allow archiving the final published version. If a post-print (author's peer-reviewed manuscript) is allowed and available, or publisher policy changes, the item will be deposited.