On the extra edge-connectivity of hypercubes

被引:4
作者
Zhang Ming-zu [1 ]
Meng Ji-xiang [1 ]
Yang Wei-hua [2 ]
机构
[1] Xinjiang Univ, Coll Math & Syst Sci, Urumqi 830046, Peoples R China
[2] Taiyuan Univ Technol, Dept Math, Taiyuan 030024, Peoples R China
基金
中国国家自然科学基金;
关键词
Edge fault tolerance; Extra edge-connectivity; Hypercube; FAULT-TOLERANCE;
D O I
10.1007/s11766-016-3247-9
中图分类号
O29 [应用数学];
学科分类号
070104 ;
摘要
The classical hypercube structure is a popular topological architecture in parallel computing environments and a large number of variations based on the hypercube were posed in the past three decades. Reliability evaluation of systems is important to the design and maintenance of multiprocessor systems. The h-extra edge-connectivity of graph G(V,E) is a kind of measure for the reliability of interconnection systems, which is defined as the minimum cardinality of a subset of edge set, if any, whose deletion disconnects G and such that every remaining component has at least h vertices. This paper shows that the h-extra edge-connectivity of the hypercube Q (n) is a constant 2 (n-1) for < h a parts per thousand currency sign 2 (n-1), and n a parts per thousand yen 4, which extends the result of ["Bounding the size of the subgraph induced by m vertices and extra edge-connectivity of hypercubes, Discrete Applied Mathematics, 2013, 161(16): 2753-2757"].
引用
收藏
页码:198 / 204
页数:7
相关论文
共 13 条