On fault-tolerant embedding of Hamiltonian cycles, linear arrays and ringsin a Flexible Hypercube

The Hamiltonian cycle of a Flexible Hypercube graph network is investigated in this paper. The result can readily be used in the optimal embedding of a linear array (or a ring) of processors in a faulty Flexible Hypercube. Th ere are embedding algorithms proposed in this paper. These embedding algori thms show a ring with any number of nodes that can be embedded into a fault y Flexible Hypercube with load 1, congestion 1 and dilation 3 such that O(n (2) - ([log(2) m])(2)) faults can be tolerated, where n is the dimension of the Flexible Hypercube and m is the number of nodes of the ring. (C) 2000 Elsevier Science B.V. All rights reserved.