The forwarding diameter of graphs Original Research Article

A routing R in a graph G is a set of paths {Rxy : x, y ϵ V(G)} where, for each ordered pair of vertices (x, y), Rxy links x to y. The load ξ(G, R, x) of a vertex x in the routing R is the number of paths of R for which x is an interior vertex. We define the forwarding diameter μ(G, R) of the pair (G, R) by μ(G, R)=maxx,y∑zϵRxy−{x,y}ξ(G,R,Z) and the forwarding diameter μ(G) of G as the minimum of μ(G, R) taken over all possible routings. In this paper, the introduction of the parameter μ(G) is motivated by a natural model of message transmission in networks and we present several properties of μ(G). In particular, we study the value of μ for several families of graphs such as the hypercube and the de Bruijn graphs and we also study the connection of μ(G) with previously introduced transmission parameters.