THE EDGE-FORWARDING INDEX OF ORBITAL REGULAR GRAPHS

被引：25

作者：

SOLE, P ^{[1
]}

机构：

[1] SYRACUSE UNIV,SCH COMP & INFORMAT SCI,SYRACUSE,NY 13244

来源：

DISCRETE MATHEMATICS | 1994年 / 130卷 / 1-3期

关键词：

D O I：

10.1016/0012-365X(92)00528-Y

中图分类号：

O1 [数学];

学科分类号：

0701 ; 070101 ;

摘要：

We define a graph as orbital regular if there is a subgroup of its automorphism group that acts regularly on the set of edges of the graph as well as on all its orbits of ordered pairs of distinct vertices of the graph. For these graphs there is an explicit formula for the edge-forwarding index, an important traffic parameter for routing in interconnection networks. Using the arithmetic properties of finite fields we construct infinite families of graphs with low edge-forwarding properties. In particular, the edge-forwarding index of Paley graphs is determined. A connection with the Waring problem over finite fields and the coset weight enumeration of certain cyclic codes is established.

引用

页码：171 / 176

页数：6

共 10 条

[1]

Bannai E., 1984, ALGEBRAIC COMBINATOR

[2]

Biggs N., 1974, ALGEBRAIC GRAPH THEO

[3]

Bollobas B., 1985, RANDOM GRAPHS

[4] HOMOGENEOUS ADDITIVE CONGRUENCES [J].

DODSON, M .

PHILOSOPHICAL TRANSACTIONS OF THE ROYAL SOCIETY OF LONDON SERIES A-MATHEMATICAL AND PHYSICAL SCIENCES, 1967, 261 (1119) :163-&

[5]

Dodson MM., 1976, ACTA ARITH, V30, P159

[6]

DORNSTETTER JL, 1984, LECTURE NOTES COMPUT, V228

[7] ON THE COVERING RADIUS OF CYCLIC LINEAR CODES AND ARITHMETIC CODES [J].

HELLESETH, T .

DISCRETE APPLIED MATHEMATICS, 1985, 11 (02) :157-173

[8] ON FORWARDING INDEXES OF NETWORKS [J].

HEYDEMANN, MC ;

MEYER, JC ;

SOTTEAU, D .

DISCRETE APPLIED MATHEMATICS, 1989, 23 (02) :103-123

[9]

MacWilliams F. J., 1981, THEORY ERROR CORRECT

[10]

SOLE P, UNPUB EXPLICIT CONST

← 1 →