DETERMINATION OF HAMILTONIAN CYCLES IN CUBE-BASED NETWORKS USING GENERALIZED GRAY CODES

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 convent ional GCs by allowing the successive codewords to have a Hamming dista nce of greater than one when necessary. This generalization provides a useful methodology for solving such problems as: embedding, subnetwor k allocation and deallocation, and fault tolerant routing for nonstand ard cube-based networks. To demonstrate the usefulness of this GC char acterization, we focus on the problem of ring (or linear array) embedd ing 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 th e Hamiltonian paths (cycles) in the cube-based networks. Using the uni fied link label representation, Gray Codes are derived for the aforeme ntioned networks. The available distinct GCs for each network are furt her enumerated. The GCs obtained as such render Hamiltonian cycles For each cube-based topology, thus providing embedding of rings (or linea r arrays) of maximum size onto the cube. It is believed that the gener alized GCs introduced here can be employed to solve many other problem s in networks whose connectivity is defined by the binary labels of no des.