On ring embedding in hypercubes with faulty nodes and links

In this paper, we show that in an it-dimensional hypercube Q(n) with f(n) faulty nodes and f(e) faulty edges, such that f(n) + f(e) less than or equal to n - 1, a ring of length 2(n) - 2f(n) can be embedded avoiding the faulty elements when f(n) > 0 or f(e) < n - 1. When f(n) = 0 and f(e) = n - 1, if all the faulty edges are not incident on the same node, a Hamiltonian cycle can be embedded avoiding the faulty elements when it greater than or equal to 4. For a Q(3), however, if f(n) = 0 and f(e) = 2, a Hamiltonian cycle might not exist even when all faulty edges are not incident on the same node. We show that a ring of size 6 can be embedded in that case. When f(n) = 0 and f(e) = n - 1, if all the faulty edges are incident on the same node, clearly a Hamiltonian cycle cannot exist and we show that a ring of size 2(n) - 2 can be embedded. This generalizes;I recent result of Tseng (1996) where the number of edge faults were assumed not to exceed it - 4. (C) 1998 Elsevier Science B.V. All rights reserved.