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

作者：Gu, Mei-Mei; Hao, Rong-Xia^*

来源：Ars Combinatoria, 2018, 140: 45-61.

• Balanced hypercube
• Cycle embedding
• Fault tolerance
• Interconnection network

Let F-v (resp. F-e) be the set of faulty vertices (resp. faulty edges) in the n-dimensional balanced hypercube BHn. Fault-tolerant Hamiltonian laceability in BHn, with at most 2n - 2 faulty edges is obtained in [Inform. Sci. 300 (2015) 20-27]. The existence of edge-Hamiltonian cycles in BHn - F-e for vertical bar F-e vertical bar <= 2n - 2 are gotten in [Appl. Math. Comput. 244 (2014) 447-456]. Up to now, almost all results about fault-tolerance in BHn with only faulty vertices or only faulty edges. In this paper, we consider fault-tolerant cycle embedding of BHn with both faulty vertices and faulty edges, and prove that there exists a fault-free cycle of length 2(2n) - 2 vertical bar F-v vertical bar in BHn with vertical bar F-v vertical bar + vertical bar F-e vertical bar <= 2n - 2 and vertical bar F-v vertical bar <= n - 1 for n >= 2. Since BHn is a bipartite graph with two partite sets of equal size, the cycle of a length 2(2n) - 2 vertical bar F-v vertical bar is the longest in the worst-case.

• 出版日期2018-7
• 单位北京交通大学