Fault-tolerant cycle embedding in the hypercube with more both faulty vertices and faulty edges

摘要

Let f_v (respectively, f_e) denote the number of faulty vertices (respectively, edges) in an n-dimensional hypercube. In this paper, we show that a fault-free cycle of length of at least 2~n - 2f_v can be embedded in an n-dimensional hypercube with f_e ≤ n - 2 and f_v + f_e ≤ 2n - 4. Our result not only improves the previously best known result of [A. Sen, A. Sengupta, S. Bandyopadhyay, On some topological properties of hypercube, incomplete hypercube and supercube, in: Proceedings of the International Parallel Processing Symposium, Newport Beach, April, 1993, pp. 636-642] where f_v > 0 or f_e ≤ n - 2 and f_v + f_e ≤ n - 1 were assumed, but also extends the result of [J.-S. Fu, Fault-tolerant cycle embedding in the hypercube, Parallel Computing 29 (2003) 821-832] where only the faulty vertices are considered.