THE FORWARDING DIAMETER OF GRAPHS

A routing R in a graph G is a set of paths {R-xy : x, y is an element of V(G)} where, for each ordered pair of vertices (x, y), R-xy links x to y. The load xi(G, R, x) of a vertex x in the routing R is the numb er of paths of Ii for which x is an interior vertex. We define the for warding diameter mu(G, R) of the pair (G, R) by [GRAPHICs] and the for warding diameter mu(G) of G as the minimum of mu(G, R) taken over all possible routings. In this paper, the introduction of the parameter mu (G) is motivated by a natural model of message transmission in network s and we present several properties of mu(G). In particular, we study the value of mu for several families of graphs such as the hypercube a nd the de Bruijn graphs and we also study the connection of mu(G) with previously introduced transmission parameters. 1998 Published by Else vier Science B.V. All rights reserved.