On the Day-Tripathi orientation of the star graphs: Connectivity

被引：15

作者：

Cheng, E ^{[1
]}

Lipman, MJ ^{[1
]}

机构：

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

来源：

INFORMATION PROCESSING LETTERS | 2000年 / 73卷 / 1-2期

关键词：

interconnection networks; connectivity;

D O I：

10.1016/S0020-0190(99)00155-6

中图分类号：

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

学科分类号：

0812 ;

摘要：

Day and Tripathi (1993) proposed an assignment of directions on the star graphs and derived attractive properties for the resulting directed graphs. An important property is that they are strongly connected. In this short paper, we show that the Day-Tripathi orientations are in fact maximally are-connected when n is odd. For n is even, they can be augmented to maximally arc-connected digraphs by adding a minimum set of arcs. (C) 2000 Elsevier Science B.V. All rights reserved.

引用

页码：5 / 10

页数：6

共 12 条

[1]

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

[2]

Bauer D., 1981, THEORY APPL GRAPHS, P89

[3]

Chartrand G., 1993, Applied and algorithmic graph theory

[4]

CHENG E, IN PRESS NETWORKS

[5]

Cheng E., 1998, 983 OAKL U

[6]

Chern SC, 1995, LECT NOTES COMPUT SC, V959, P490, DOI 10.1007/BFb0030870

[7]

Chou C.-H., 1990, Proceedings of Supercomputing '90 (Cat. No.90CH2916-5), P254, DOI 10.1109/SUPERC.1990.130028

[8] VERTEX-SYMMETRICAL DIGRAPHS WITH SMALL-DIAMETER [J].

COMELLAS, F ;

FIOL, MA .

DISCRETE APPLIED MATHEMATICS, 1995, 58 (01) :1-11

[9] UNIDIRECTIONAL STAR GRAPHS [J].

DAY, K ;

TRIPATHI, A .

INFORMATION PROCESSING LETTERS, 1993, 45 (03) :123-129

[10]

Jwo JS, 1998, NETWORKS, V32, P307, DOI 10.1002/(SICI)1097-0037(199812)32:4<307::AID-NET7>3.0.CO

← 1 2 →