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

被引:0
作者
Gu, Mei-Mei [1 ]
Hao, Rong-Xia [1 ]
机构
[1] Beijing Jiaotong Univ, Dept Math, Beijing 100044, Peoples R China
基金
中国国家自然科学基金;
关键词
Balanced hypercube; Cycle embedding; Fault tolerance; Interconnection network; HAMILTONIAN LACEABILITY; PATHS;
D O I
暂无
中图分类号
O1 [数学];
学科分类号
0701 ; 070101 ;
摘要
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.
引用
收藏
页码:45 / 61
页数:17
相关论文
共 50 条
[41]   One-to-one disjoint path covers in hypercubes with faulty edges [J].
Wang, Fan ;
Zhao, Weisheng .
JOURNAL OF SUPERCOMPUTING, 2019, 75 (08) :5583-5595
[42]   Fault-tolerant edge-bipancyclicity of faulty hypercubes under the conditional-fault model [J].
Yang, Da-Wei ;
Feng, Yan-Quan ;
Kwak, Jin Ho ;
Zhou, Jin-Xin .
INFORMATION SCIENCES, 2016, 329 :317-328
[43]   A Fault-Tolerant and Heuristic Routing Algorithm for Faulty Hypercubes [J].
闵有力 ;
闵应骅 .
Journal of Computer Science and Technology, 1995, (06) :536-544
[44]   Panconnectivity of n-dimensional torus networks with faulty vertices and edges [J].
Yuan, Jun ;
Liu, Aixia ;
Wu, Hongmei ;
Li, Jing .
DISCRETE APPLIED MATHEMATICS, 2013, 161 (03) :404-423
[45]   Paired many-to-many disjoint path covers of hypercubes with faulty edges [J].
Chen, Xie-Bin .
INFORMATION PROCESSING LETTERS, 2012, 112 (03) :61-66
[46]   Recursive fault-tolerance of Fibonacci cube in hypercubes [J].
Gregor, Petr .
DISCRETE MATHEMATICS, 2006, 306 (13) :1327-1341
[47]   The Local Diagnosability of Folded Hypercubes with Conditional Faulty Edges Under the PMC Model [J].
Wang, Shiying ;
Fan, Changchang ;
Ma, Xiaolei ;
Ren, Yunxia .
JOURNAL OF INTERCONNECTION NETWORKS, 2022, 22 (02)
[48]   Fault-tolerance and unique identification of vertices and edges in a graph: The fault-tolerant mixed metric dimension [J].
Khan, Asad ;
Ali, Sikander ;
Hayat, Sakander ;
Azeem, Muhammad ;
Zhong, Yubin ;
Zahid, Manzoor Ahmad ;
Alenazi, Mohammed J. F. .
JOURNAL OF PARALLEL AND DISTRIBUTED COMPUTING, 2025, 197
[49]   Unicast in hypercubes with large number of faulty nodes [J].
Gu, QP ;
Peng, ST .
IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS, 1999, 10 (10) :964-975
[50]   All-to-all broadcasting in faulty hypercubes [J].
Park, S ;
Bose, B .
IEEE TRANSACTIONS ON COMPUTERS, 1997, 46 (07) :749-755