Linearly many faults in Cayley graphs generated by transposition trees

被引：104

作者：

Cheng, Eddie ^{[1
]}

Liptak, Laszlo ^{[1
]}

机构：

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

来源：

INFORMATION SCIENCES | 2007年 / 177卷 / 22期

关键词：

interconnection networks; star graph; bubble-sort graph; Cayley graphs; transposition tree; superconnectedness;

D O I：

10.1016/j.ins.2007.05.034

中图分类号：

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

学科分类号：

0812 ;

摘要：

We prove that when linearly many vertices are deleted in a Cayley graph generated by a transposition tree, the resulting graph has a large connected component containing almost all remaining vertices. (C) 2007 Elsevier Inc. All rights reserved.

引用

页码：4877 / 4882

页数：6

共 38 条

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

ARAKI T, 2006, HYPER HAMILTONIAN LA, P121

[4] A WELL-BEHAVED ENUMERATION OF STAR GRAPHS [J].

BAGHERZADEH, N ;

DOWD, M ;

LATIFI, S .

IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS, 1995, 6 (05) :531-535

[5] Panconnectivity, fault-tolerant Hamiltonicity and Hamiltonian-connectivity in alternating group graphs [J].

Chang, JM ;

Yang, JS .

NETWORKS, 2004, 44 (04) :302-310

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

[7]

CHEN YC, UNPUB RESTRICTED CON

[8] Maximal vertex-connectivity of (Sn,k)over-right-arrow [J].

Cheng, E ;

Lindsey, WA ;

Steffy, DE .

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

[9] On the Day-Tripathi orientation of the star graphs: Connectivity [J].

Cheng, E ;

Lipman, MJ .

INFORMATION PROCESSING LETTERS, 2000, 73 (1-2) :5-10

[10]

Cheng E, 2000, NETWORKS, V35, P139, DOI 10.1002/(SICI)1097-0037(200003)35:2<139::AID-NET4>3.0.CO

← 1 2 3 4 →