Fault-tolerance of balanced hypercubes with faulty vertices and faulty edges

Abstract

Let $F_v$ (resp. $F_e$) be the set of faulty vertices (resp. faulty edges) in the $n$-dimensional balanced hypercube $B{H}_n$. Fault-tolerant Hamiltonian laceability in $B{H}_n$ with at most $2n-2$ faulty edges is obtained in [Inform. Sci. 300 (2015) 20--27]. The existence of edge-Hamiltonian cycles in $B{H}_n-F_e$ for $|F_e|\le 2n-2$ are gotten in [Appl. Math. Comput. 244 (2014) 447--456]. Up to now, almost all results about fault-tolerance in $B{H}_n$ with only faulty vertices or only faulty edges. In this paper, we consider fault-tolerant cycle embedding of $B{H}_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 $B{H}_n$ with $|F_v|+|F_e|\le 2n-2$ and $|F_v|\le n-1$ for $n\ge 2$. Since $B{H}_n$ is a bipartite graph with two partite sets of equal size, the cycle of a length $2^{2n}-2|F_v|$ is the longest in the worst-case.

17 pages, 5 figures, 1 table