LINEARLY MANY FAULTS IN (n, k)-STAR GRAPHS

被引：39

作者：

Yuan, Allen ^{[2
]}

Cheng, Eddie ^{[1
]}

Liptak, Laszlo ^{[1
]}

机构：

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

[2] Detroit Country Day Sch, Beverly Hills, MI 48025 USA

来源：

INTERNATIONAL JOURNAL OF FOUNDATIONS OF COMPUTER SCIENCE | 2011年 / 22卷 / 07期

关键词：

(n; k)-star graphs; structural properties; fault-tolerant; MAXIMAL CONNECTED COMPONENT; SUPER-CONNECTIVITY; HYPERCUBE;

D O I：

10.1142/S0129054111008994

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

The star graph proposed by [1] has many advantages over the n-cube. However it suffers from having large gaps in the number of possible vertices. The (n, k)-star graph was proposed in [18] to address this issue. Since it is a generalization of the star graph, it retains many of the nice properties of the star graph. There are many different measures of structural integrity of interconnection networks. In this paper, we prove results of the following type for the (n, k)-star graph. If n + (r - 1)k - g(r) vertices are deleted from an (n, k)-star graph, the resulting graph will either be connected or has a large component and small components having at most r - 1 vertices in total. Additional results on conditional vertex connectivity and cycle connectivity will also be given.

引用

页码：1729 / 1745

页数：17

共 27 条

[1]

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

[2] On the connectivity and superconnected graphs with small diameter [J].

Balbuena, C. ;

Marshall, K. ;

Montejano, L. P. .

DISCRETE APPLIED MATHEMATICS, 2010, 158 (05) :397-403

[3]

Bauer D., 1981, The Theory and Application of Graphs, P89

[4] CIRCULANTS AND THEIR CONNECTIVITIES [J].

BOESCH, F ;

TINDELL, R .

JOURNAL OF GRAPH THEORY, 1984, 8 (04) :487-499

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

BOESCH, FT .

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

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

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

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

Cheng, E ;

Lipman, MJ .

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

[9]

Cheng E, 2001, ARS COMBINATORIA, V59, P107

[10]

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

← 1 2 3 →