𝔖 Bobbio Scriptorium
✦   LIBER   ✦

The edge-forwarding index of orbital regular graphs

✍ Scribed by Patrick Solé

Publisher
Elsevier Science
Year
1994
Tongue
English
Weight
351 KB
Volume
130
Category
Article
ISSN
0012-365X

No coin nor oath required. For personal study only.

✦ Synopsis

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 edgeforwarding 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. R

📜 SIMILAR VOLUMES

Almost regular edge colorings and regula
Almost regular edge colorings and regular decompositions of complete graphs
✍ Darryn Bryant; Barbara Maenhaut 📂 Article 📅 2008 🏛 John Wiley and Sons 🌐 English ⚖ 127 KB

## Abstract For __k__ = 1 and __k__ = 2, we prove that the obvious necessary numerical conditions for packing __t__ pairwise edge‐disjoint __k__‐regular subgraphs of specified orders __m__~1~,__m__~2~,… ,__m__~t~ in the complete graph of order __n__ are also sufficient. To do so, we present an edge

The generalized acyclic edge chromatic n
The generalized acyclic edge chromatic number of random regular graphs
✍ Stefanie Gerke; Catherine Greenhill; Nicholas Wormald 📂 Article 📅 2006 🏛 John Wiley and Sons 🌐 English ⚖ 224 KB 👁 1 views

## Abstract The __r__‐acyclic edge chromatic number of a graph is defined to be the minimum number of colors required to produce an edge coloring of the graph such that adjacent edges receive different colors and every cycle __C__ has at least min(|__C__|, __r__) colors. We show that (__r__ − 2)__d

Orbits on vertices and edges of finite g
Orbits on vertices and edges of finite graphs
✍ Dominique Buset 📂 Article 📅 1985 🏛 Elsevier Science 🌐 English ⚖ 134 KB

Given two integers v > 0 and e/> 0, we prove that there exists a finite graph (resp. a finite connected graph) whose automorphism group has exactly v orbits on the set of vertices and e orbits on the set of edges if and only if v ~< 2e + 1 (resp. v ~< e + 1).