Fault-Tolerant Cycle Embedding in Balanced Hypercubes with Faulty Vertices and Faulty Edges

摘要

Let F_v (resp. F_e) be the set of faulty vertices (resp. faulty edges) in the n-dimensional balanced hypercube BH_n. The edge-bipancyclicity of BH_n - F_v for |F_v| ≤ n - 1 had been proved in [Inform. Sci. 288 (2014) 449-461]. The existence of edge-Hamiltonian cycles in BH_n - F_e for |F_e| ≤ 2n - 2 were obtained in [Appl. Math. Comput. 244 (2014) 447-456]. In this paper, we consider fault-tolerant cycle embedding of BH_n with both faulty vertices and faulty edges, and prove that there exists a fault-free cycle of length 2~(2n) - 2|F_v| in BH_n with |F_v| + |F_e| ≤ 2n - 3 and |F_v| ≤ n - 1 for n ≥ 2.