Linearly Many Faults in 2-Tree-Generated Networks

被引：56

作者：

Cheng, Eddie ^{[1
]}

Liptak, Laszlo ^{[1
]}

Sala, Fred ^{[2
]}

机构：

[1] Oakland Univ, Dept Math & Stat, Rochester, MI 48309 USA

[2] Univ Michigan, Ann Arbor, MI 48109 USA

来源：

NETWORKS | 2010年 / 55卷 / 02期

关键词：

interconnection network; Cayley graph; alternating group graph; fault resiliency; MAXIMAL CONNECTED COMPONENT; INTERCONNECTION NETWORKS; STAR GRAPHS; SUPER-CONNECTIVITY; ALTERNATING GROUP; HYPERCUBE; VERTICES; TREES;

D O I：

10.1002/net.20319

中图分类号：

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

学科分类号：

0812 ;

摘要：

In this article we consider a class of Cayley graphs that are generated by certain 3-cycles on the alternating group A(n). These graphs are generalizations of the alternating group graph AG(n). We look at the case when the 3-cycles form a "tree-like structure," and analyze its fault resiliency. We present a number of structural theorems and prove that even with linearly many vertices deleted, the remaining graph has a large connected component containing almost all vertices. (C) 2009 Wiley Periodicals, Inc. NETWORKS, Vol. 55(2),90-98 2010

引用

页码：90 / 98

页数：9

共 22 条

[1]

Akers S. B., 1987, Proceedings of the 1987 International Conference on Parallel Processing, P393

[2]

Beineke L.W., 1969, J. Combin. Theory, V6, P200

[3] PROPERTIES AND CHARACTERIZATIONS OF K-TREES [J].

BEINEKE, LW ;

PIPPERT, RE .

MATHEMATIKA, 1971, 18 (35) :141-&

[4] Restricted connectivity for three families of interconnection networks [J].

Chen, Y-Chuang ;

Tan, Jimmy J. M. .

APPLIED MATHEMATICS AND COMPUTATION, 2007, 188 (02) :1848-1855

[5] Super-connectivity and super-edge-connectivity for some interconnection networks [J].

Chen, YC ;

Tan, JJM ;

Hsu, LH ;

Kao, SS .

APPLIED MATHEMATICS AND COMPUTATION, 2003, 140 (2-3) :245-254

[6] Increasing the connectivity of the star graphs [J].

Cheng, E ;

Lipman, MJ .

NETWORKS, 2002, 40 (03) :165-169

[7]

Cheng E, 2001, ARS COMBINATORIA, V59, P107

[8]

Cheng E., 2000, C NUMER, V146, P97

[9]

Cheng E., 2006, CONGR NUMER CONF J N, V180, P81

[10] Hamiltonian connectivity of 2-tree-generated networks [J].

Cheng, Eddie ;

Lipman, Marc J. ;

Liptak, Laszlo ;

Stiebel, David .

MATHEMATICAL AND COMPUTER MODELLING, 2008, 48 (5-6) :787-804

← 1 2 3 →