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 条
[31]   Extended Fault-Tolerant Cycle Embedding in Faulty Hypercubes [J].
Hsieh, Sun-Yuan ;
Chang, Nai-Wen .
IEEE TRANSACTIONS ON RELIABILITY, 2009, 58 (04) :702-710
[32]   Cycles in highly faulty hypercubes [J].
Yang, MC ;
Tan, JJM ;
Hsu, LH .
FCS '05: Proceedings of the 2005 International Conference on Foundations of Computer Science, 2005, :101-107
[33]   Path embedding in faulty hypercubes [J].
Ma, Meijie ;
Liu, Guizhen ;
Pan, Xiangfeng .
APPLIED MATHEMATICS AND COMPUTATION, 2007, 192 (01) :233-238
[34]   Vertex-disjoint paths joining adjacent vertices in faulty hypercubes [J].
Cheng, Dongqin .
THEORETICAL COMPUTER SCIENCE, 2019, 795 :219-224
[35]   Fault-tolerant Hamiltonicity of hypercubes with faulty subcubes [J].
Sabir, Eminjan ;
Meng, Jixiang .
INFORMATION PROCESSING LETTERS, 2021, 172
[36]   Structure fault tolerance of balanced hypercubes [J].
Liu, Heqin ;
Cheng, Dongqin .
THEORETICAL COMPUTER SCIENCE, 2020, 845 :198-207
[37]   Structure fault tolerance of balanced hypercubes [J].
Yang, Yuxing ;
Li, Xiaohui ;
Li, Jing .
JOURNAL OF SUPERCOMPUTING, 2021, 77 (04) :3885-3898
[38]   Hamiltonian cycles of balanced hypercube with disjoint faulty edges [J].
Lan, Ting ;
Lu, Huazhong .
INFORMATION PROCESSING LETTERS, 2025, 187
[39]   Conditional Fault-tolerant Cycles in Folded Hypercubes With Faulty Elements [J].
Zheng, Jian-Wei ;
Guo, Da-chang ;
Liang, Ri-Fei .
SIXTH INTERNATIONAL CONFERENCE ON MACHINE VISION (ICMV 2013), 2013, 9067
[40]   Hamiltonian cycles in hypercubes with 2n-4 faulty edges [J].
Szepietowski, Andrzej .
INFORMATION SCIENCES, 2012, 215 :75-82