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 条
  • [21] Odd cycles embedding on folded hypercubes with conditional faulty edges
    Cheng, Dongqin
    Hao, Rong-Xia
    Feng, Yan-Quan
    INFORMATION SCIENCES, 2014, 282 : 180 - 189
  • [22] Embedding even cycles on folded hypercubes with conditional faulty edges
    Cheng, Dongqin
    Hao, Rong-Xia
    Feng, Yan-Quan
    INFORMATION PROCESSING LETTERS, 2015, 115 (12) : 945 - 949
  • [23] Fault-tolerant cycle embedding in the faulty hypercubes
    Cheng, Dongqin
    Guo, Dachang
    INFORMATION SCIENCES, 2013, 253 : 157 - 162
  • [24] Hamiltonian cycles and paths in hypercubes with disjoint faulty edges
    Dybizbanski, Janusz
    Szepietowski, Andrzej
    INFORMATION PROCESSING LETTERS, 2021, 172 (172)
  • [25] Fault-free cycles passing through prescribed paths in hypercubes with faulty edges
    Tsai, Chang-Hsiung
    APPLIED MATHEMATICS LETTERS, 2009, 22 (06) : 852 - 855
  • [26] Many-to-many disjoint paths in hypercubes with faulty vertices
    Li, Xiang Jun
    Liu, Bin
    Ma, Meijie
    Xu, Jun-Ming
    DISCRETE APPLIED MATHEMATICS, 2017, 217 : 229 - 242
  • [27] Generalized fault-tolerance for enhanced hypercubes
    Ma, Meijie
    Li, Xiang-Jun
    Wang, Guijuan
    Zan, Yongli
    DISCRETE APPLIED MATHEMATICS, 2024, 342 : 244 - 252
  • [28] Small matchings extend to Hamiltonian cycles in hypercubes with disjoint faulty edges
    Wang, Fan
    DISCRETE APPLIED MATHEMATICS, 2025, 363 : 16 - 26
  • [29] Edge-bipancyclicity of a hypercube with faulty vertices and edges
    Hsieh, Sun-Yuan
    Shen, Tzu-Hsiung
    DISCRETE APPLIED MATHEMATICS, 2008, 156 (10) : 1802 - 1808
  • [30] Extended Fault-Tolerant Cycle Embedding in Faulty Hypercubes
    Hsieh, Sun-Yuan
    Chang, Nai-Wen
    IEEE TRANSACTIONS ON RELIABILITY, 2009, 58 (04) : 702 - 710