Fault resiliency of Cayley graphs generated by transpositions

被引：44

作者：

Cheng, Eddie ^{[1
]}

Liptak, Laszlo ^{[1
]}

机构：

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

来源：

INTERNATIONAL JOURNAL OF FOUNDATIONS OF COMPUTER SCIENCE | 2007年 / 18卷 / 05期

关键词：

interconnection networks; connectivity; Cayley graphs;

D O I：

10.1142/S0129054107005108

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

The star graph S., proposed by [1], has many advantages over the n-cube. It is shown in [2] that when a large number of vertices are deleted from S., the resulting graph can have at most two components, one of which is small. In this paper, we show that Cayley graphs generated by transpositions have this property.

引用

页码：1005 / 1022

页数：18

共 14 条

[1]

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

[2] A GROUP-THEORETIC MODEL FOR SYMMETRIC INTERCONNECTION NETWORKS [J].

AKERS, SB ;

KRISHNAMURTHY, B .

IEEE TRANSACTIONS ON COMPUTERS, 1989, 38 (04) :555-566

[3] Hyper hamiltonian laceability of Cayley graphs generated by transpositions [J].

Araki, Toru .

NETWORKS, 2006, 48 (03) :121-124

[4]

Bauer D., 1981, THEORY APPL GRAPHS, P89

[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] Maximal vertex-connectivity of (Sn,k)over-right-arrow [J].

Cheng, E ;

Lindsey, WA ;

Steffy, DE .

NETWORKS, 2005, 46 (03) :154-162

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

Cheng, E ;

Lipman, MJ .

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

[8]

Cheng E, 2001, ARS COMBINATORIA, V59, P107

[9]

Cheng E., 2002, J INTERCONNECT NETW, V3, P19

[10]

CHENG E, 2005, C NUMERANTIUM, V175, P117

← 1 2 →