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

preprint2016arXivOpen access

Abstract

Let FvF_{v} (resp. FeF_e) be the set of faulty vertices (resp. faulty edges) in the nn-dimensional balanced hypercube BHnBH_n. Fault-tolerant Hamiltonian laceability in BHnBH_n with at most 2n−22n-2 faulty edges is obtained in [Inform. Sci. 300 (2015) 20--27]. The existence of edge-Hamiltonian cycles in BHn−FeBH_n-F_e for ∣Fe∣≤2n−2|F_e|\leq 2n-2 are gotten in [Appl. Math. Comput. 244 (2014) 447--456]. Up to now, almost all results about fault-tolerance in BHnBH_n with only faulty vertices or only faulty edges. In this paper, we consider fault-tolerant cycle embedding of BHnBH_n with both faulty vertices and faulty edges, and prove that there exists a fault-free cycle of length 22n−2∣Fv∣2^{2n}-2|F_v| in BHnBH_n with ∣Fv∣+∣Fe∣≤2n−2|F_v|+|F_e|\leq 2n-2 and ∣Fv∣≤n−1|F_v|\leq n-1 for n≥2n\geq 2. Since BHnBH_n is a bipartite graph with two partite sets of equal size, the cycle of a length 22n−2∣Fv∣2^{2n}-2|F_v| is the longest in the worst-case.

Explore this paper’s authors, topics and related work.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Reviews 0

Write a reviewWrite

No reviews yet.

Discussion 0

Add a commentWrite

No comments yet.