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 条
  • [11] Various cycles embedding in faulty balanced hypercubes
    Cheng, Dongqin
    Hao, Rong-Xia
    INFORMATION SCIENCES, 2015, 297 : 140 - 153
  • [12] Paired many-to-many two-disjoint path cover of balanced hypercubes with faulty edges
    Huazhong Lü
    The Journal of Supercomputing, 2019, 75 : 400 - 424
  • [13] Matchings extend to Hamiltonian cycles in hypercubes with faulty edges
    Xie-Bin Chen
    Frontiers of Mathematics in China, 2019, 14 : 1117 - 1132
  • [14] Fault-free Hamiltonian paths passing through prescribed linear forests in balanced hypercubes with faulty links
    Yang, Yuxing
    Song, Ningning
    THEORETICAL COMPUTER SCIENCE, 2023, 939 : 161 - 169
  • [15] Hamiltonian cycles of balanced hypercube with more faulty edges
    Lan, Ting
    Lu, Huazhong
    THEORETICAL COMPUTER SCIENCE, 2023, 947
  • [16] A note on fault-free mutually independent Hamiltonian cycles in hypercubes with faulty edges
    Kueng, Tz-Liang
    Lin, Cheng-Kuan
    Liang, Tyne
    Tan, Jimmy J. M.
    Hsu, Lih-Hsing
    JOURNAL OF COMBINATORIAL OPTIMIZATION, 2009, 17 (03) : 312 - 322
  • [17] A note on fault-free mutually independent Hamiltonian cycles in hypercubes with faulty edges
    Tz-Liang Kueng
    Cheng-Kuan Lin
    Tyne Liang
    Jimmy J. M. Tan
    Lih-Hsing Hsu
    Journal of Combinatorial Optimization, 2009, 17 : 312 - 322
  • [18] Long cycles in hypercubes with optimal number of faulty vertices
    Fink, Jiri
    Gregor, Petr
    JOURNAL OF COMBINATORIAL OPTIMIZATION, 2012, 24 (03) : 240 - 265
  • [19] Odd cycles embedding on folded hypercubes with conditional faulty edges
    Cheng, Dongqin
    Hao, Rong-Xia
    Feng, Yan-Quan
    INFORMATION SCIENCES, 2014, 282 : 180 - 189
  • [20] 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