On the 3-Extra Connectivity of Enhanced Hypercubes

被引：0

作者：

Zhai, Liyang ^{[1
]}

Xu, Liqiong ^{[1
]}

Yin, Shanshan ^{[1
]}

机构：

[1] Jimei Univ, Sch Sci, Xiamen 361021, Fujian, Peoples R China

来源：

PARALLEL PROCESSING LETTERS | 2021年 / 31卷 / 04期

基金：

中国国家自然科学基金;

关键词：

Enhanced hypercube; hypercube; g-extra connectivity; fault tolerance; EXTRA EDGE-CONNECTIVITY; RELIABILITY-ANALYSIS; TERMS; EXTRACONNECTIVITY; DIAGNOSABILITY; COMPONENT;

D O I：

10.1142/S012962642150016X

中图分类号：

TP39 [计算机的应用];

学科分类号：

081203 ; 0835 ;

摘要：

Reliability evaluation of interconnection networks is of significant importance to the design and maintenance of interconnection networks. The extra connectivity is an important parameter for the reliability evaluation of interconnection networks. Given a graph G and a positive integer g, the g-extra connectivity, denoted by kappa(g)(G), is the minimum cardinality of a set of vertices in G, if exists, whose deletion disconnects G and leaves each remaining component with at least (g + 1) vertices. In this paper, we show that the 3-extra connectivity of the (n,k)-enhanced hypercube is (4n - 5) for n >= 7 and 1 <= k <= n - 6. Some previous results in [IEEE Trans. Comput. 63 (2014) 1594-1600] and [Theor. Comput. Sci. 799 (2019) 22-31] are extended.

引用

页数：15

共 25 条

[1]

Bondy J. A., 2008, Graph Theory

[2] On 3-Extra Connectivity and 3-Extra Edge Connectivity of Folded Hypercubes [J].

Chang, Nai-Wen ;

Tsai, Cheng-Yen ;

Hsieh, Sun-Yuan .

IEEE TRANSACTIONS ON COMPUTERS, 2014, 63 (06) :1593-1599

[3] PROPERTIES AND PERFORMANCE OF FOLDED HYPERCUBES [J].

ELAMAWY, A ;

LATIFI, S .

IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS, 1991, 2 (01) :31-42

[4] GENERALIZED MEASURES OF FAULT TOLERANCE WITH APPLICATION TO N-CUBE NETWORKS [J].

ESFAHANIAN, AH .

IEEE TRANSACTIONS ON COMPUTERS, 1989, 38 (11) :1586-1591

[5] On the extraconnectivity of graphs [J].

Fabrega, J ;

Fiol, MA .

DISCRETE MATHEMATICS, 1996, 155 (1-3) :49-57

[6] CONDITIONAL CONNECTIVITY [J].

HARARY, F .

NETWORKS, 1983, 13 (03) :347-357

[7] The extra connectivity of enhanced hypercubes [J].

Li, Jin'e ;

Huang, Yanze ;

Lin, Limei ;

Yu, Hui ;

Chen, Riqing .

INTERNATIONAL JOURNAL OF PARALLEL EMERGENT AND DISTRIBUTED SYSTEMS, 2020, 35 (01) :91-102

[8] The Relationship Between g-Restricted Connectivity and g-Good-Neighbor Fault Diagnosability of General Regular Networks [J].

Lin, Limei ;

Hsieh, Sun-Yuan ;

Chen, Riqing ;

Xu, Li ;

Lee, Chia-Wei .

IEEE TRANSACTIONS ON RELIABILITY, 2018, 67 (01) :285-296

[9] The h-extra connectivity of k-ary n-cubes [J].

Liu, Aixia ;

Wang, Shiying ;

Yuan, Jun ;

Ma, Xue .

THEORETICAL COMPUTER SCIENCE, 2019, 784 :21-45

[10]

Liu H., 2008, J SYST SCI INF, V6, P251

← 1 2 3 →