On 3-Extra Connectivity and 3-Extra Edge Connectivity of Folded Hypercubes

被引：101

作者：

Chang, Nai-Wen ^{[1
]}

Tsai, Cheng-Yen ^{[1
]}

Hsieh, Sun-Yuan ^{[1
]}

机构：

[1] Natl Cheng Kung Univ, Dept Comp Sci & Informat Engn, Tainan 701, Taiwan

来源：

IEEE TRANSACTIONS ON COMPUTERS | 2014年 / 63卷 / 06期

关键词：

Interconnected networks; connectivity; extra connectivity; extra edge connectivity; fault-tolerance; reliability; EXTRACONNECTIVITY; RELIABILITY;

D O I：

10.1109/TC.2013.10

中图分类号：

TP3 [计算技术、计算机技术];

学科分类号：

0812 ;

摘要：

Given a graph G and a non-negative integer, the g-extra connectivity (resp. g-extra edge connectivity) of G is the minimum cardinality of a set of vertices (resp. edges) in G, if it exists, whose deletion disconnects G and leaves each remaining component with more than g vertices. This study shows that the 3-extra connectivity (resp. 3-extra edge connectivity) of an n-dimensional folded hypercube is 4n - 5 for n >= 6 (resp. 4n - 4 for n >= 5). This study also provides an upper bound for the g-extra connectivity on folded hypercubes for g >= 6.

引用

页码：1593 / 1599

页数：7

共 26 条

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

ELAMAWY, A ;

LATIFI, S .

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

[2] ON COMPUTING A CONDITIONAL EDGE-CONNECTIVITY OF A GRAPH [J].

ESFAHANIAN, AH ;

HAKIMI, SL .

INFORMATION PROCESSING LETTERS, 1988, 27 (04) :195-199

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

ESFAHANIAN, AH .

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

[4]

Esmaeili T., 2012, J COMPUT, V4, P163

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

Fabrega, J ;

Fiol, MA .

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

[6] EXTRACONNECTIVITY OF GRAPHS WITH LARGE GIRTH [J].

FABREGA, J ;

FIOL, MA .

DISCRETE MATHEMATICS, 1994, 127 (1-3) :163-170

[7] Conditional diagnosability of hypercubes under the comparison diagnosis model [J].

Hsu, Guo-Huang ;

Chiang, Chieh-Feng ;

Shih, Lun-Min ;

Hsu, Lih-Hsing ;

Tan, Jimmy J. M. .

JOURNAL OF SYSTEMS ARCHITECTURE, 2009, 55 (02) :140-146

[8] w-Rabin numbers and strong w-rabin numbers of folded hypercubes [J].

Lai, Cheng-Nan ;

Chen, Gen-Huey .

NETWORKS, 2008, 51 (03) :171-177

[9] CONDITIONAL CONNECTIVITY MEASURES FOR LARGE MULTIPROCESSOR SYSTEMS [J].

LATIFI, S ;

HEGDE, M ;

NARAGHIPOUR, M .

IEEE TRANSACTIONS ON COMPUTERS, 1994, 43 (02) :218-222

[10] SIMULATION OF PM21 NETWORK BY FOLDED HYPERCUBE [J].

LATIFI, S .

IEE PROCEEDINGS-E COMPUTERS AND DIGITAL TECHNIQUES, 1991, 138 (06) :397-400

← 1 2 3 →