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
相关论文
共 26 条
[1]   EDGE-PANCYCLIC BLOCK-INTERSECTION GRAPHS [J].
ALSPACH, B ;
HARE, D .
DISCRETE MATHEMATICS, 1991, 97 (1-3) :17-24
[2]  
Bondy J.A., 1971, Journal of Combinatorial Theory, Series B, V11, P80
[3]   Various cycles embedding in faulty balanced hypercubes [J].
Cheng, Dongqin ;
Hao, Rong-Xia .
INFORMATION SCIENCES, 2015, 297 :140-153
[4]   Vertex-fault-tolerant cycles embedding in balanced hypercubes [J].
Cheng, Dongqin ;
Hao, Rong-Xia ;
Feng, Yan-Quan .
INFORMATION SCIENCES, 2014, 288 :449-461
[5]   Two node-disjoint paths in balanced hypercubes [J].
Cheng, Dongqin ;
Hao, Rong-Xia ;
Feng, Yan-Quan .
APPLIED MATHEMATICS AND COMPUTATION, 2014, 242 :127-142
[6]   A note on cycle embedding in hypercubes with faulty vertices [J].
Du, Zheng-Zhong ;
Xu, Jun-Ming .
INFORMATION PROCESSING LETTERS, 2011, 111 (12) :557-560
[7]   Longest fault-free paths in hypercubes with vertex faults [J].
Fu, JS .
INFORMATION SCIENCES, 2006, 176 (07) :759-771
[8]   Hamiltonian cycle embedding for fault tolerance in balanced hypercubes [J].
Hao, Rong-Xia ;
Zhang, Ru ;
Feng, Yan-Quan ;
Zhou, Jin-Xin .
APPLIED MATHEMATICS AND COMPUTATION, 2014, 244 :447-456
[9]   Fault-tolerant cycle embedding in the hypercube with more both faulty vertices and faulty edges [J].
Hsieh, SY .
PARALLEL COMPUTING, 2006, 32 (01) :84-91
[10]   Fault-tolerant resource placement in balanced hypercubes [J].
Huang, K ;
Wu, J .
INFORMATION SCIENCES, 1997, 99 (3-4) :159-172