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

2016/04/27 by Mei-Mei Gu, Rong‐Xia Hao, Gu, Mei-Mei +1
Computer Science · Engineering · #Combinatorics (math.CO) #FOS: Mathematics #Interconnection Networks and Systems #Radiation Effects in Electronics #Software-Defined Networks and 5G

paper · pdf · doi:10.48550/arxiv.1604.07895

openalex publication_date 2016/04/27 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

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

Related

• Optimal edge fault-tolerant-prescribed hamiltonian laceability of balanced hypercubes
• Fault-free Hamiltonian cycles in balanced hypercube with conditional edge faults
• Hamiltonian laceability with a set of faulty edges in hypercubes
• Edge-Fault Tolerance of Hypercube-like Networks
• Paired many-to-many 2-disjoint path cover of balanced hypercubes with faulty edges