The super connectivity of augmented cubes

被引：65

作者：

Ma, Meijie ^{[1
]}

Liu, Guizhen ^{[2
]}

Xu, Jun-Ming ^{[3
]}

机构：

[1] Zhejiang Normal Univ, Dept Math, Jinhua 321004, Peoples R China

[2] Shandong Univ, Sch Math & Syst Sci, Jinan 250100, Peoples R China

[3] Univ Sci & Technol China, Dept Math, Anhua 230026, Peoples R China

来源：

INFORMATION PROCESSING LETTERS | 2008年 / 106卷 / 02期

基金：

高等学校博士学科点专项科研基金; 中国博士后科学基金; 中国国家自然科学基金;

关键词：

interconnection networks; augmented cube; super connectivity; super edge-connectivity;

D O I：

10.1016/j.ipl.2007.10.005

中图分类号：

TP [自动化技术、计算机技术];

学科分类号：

0812 ;

摘要：

The augmented cube AQ(n), proposed by Choudum and Sunitha [S.A. Choudum, V. Sunitha, Augmented cubes, Networks 40 (2) (2002) 71-84], is a (2n - 1)-regular (2n - 1)-connected graph (n not equal 3). This paper determines that the super connectivity of AQ(n) is 4n - 8 for n >= 6 and the super edge-connectivity is 4n - 4 for n >= 5. That is, for n >= 6 (respectively, n >= 5), at least 4n - 8 vertices (respectively, 4n - 4 edges) of AQ(n) are removed to get a disconnected graph that contains no isolated vertices. When the augmented cube is used to model the topological structure of a large-scale parallel processing system, these results can provide more accurate measurements for reliability and fault tolerance of the system. (C) 2007 Elsevier B.V. All rights reserved.

引用

页码：59 / 63

页数：5

共 17 条

[1] SYNTHESIS OF RELIABLE NETWORKS - A SURVEY [J].

BOESCH, FT .

IEEE TRANSACTIONS ON RELIABILITY, 1986, 35 (03) :240-246

[2] Augmented cubes [J].

Choudum, SA ;

Sunitha, V .

NETWORKS, 2002, 40 (02) :71-84

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

ESFAHANIAN, AH ;

HAKIMI, SL .

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

[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]

Fan YM, 2006, ARS COMBINATORIA, V81, P369

[6] Fault hamiltonicity of augmented cubes [J].

Hsu, HC ;

Chiang, LC ;

Tan, JJM ;

Hsu, LH .

PARALLEL COMPUTING, 2005, 31 (01) :131-145

[7]

LU M, 2006, ACTA MATH APPL SIN-E, V22, P43

[8] On super edge-connectivity of Cartesian product graphs [J].

Lu, Min ;

Chen, Guo-Liang ;

Xu, Jun-Ming .

NETWORKS, 2007, 49 (02) :152-157

[9] Panconnectivity and edge-fault-tolerant pancyclicity of augmented cubes [J].

Ma, Meijie ;

Liu, Guizhen ;

Xu, Jun-Ming .

PARALLEL COMPUTING, 2007, 33 (01) :36-42

[10] On reliability of the folded hypercubes [J].

Qiang Zhu ;

Jun-Ming Xu ;

Xinmin Hou ;

Min Xu .

INFORMATION SCIENCES, 2007, 177 (08) :1782-1788

← 1 2 →