On forwarding indices of networks

AbstractA network (G,R) consists in a given undirected graph G of order n and a routing R, that is a collection of n(n-1) simple paths connecting every ordered pair of vertices of G. Chung, Coffman, Reiman and Simon defined the forwarding index ξ(G,R) of a network (G,R) as the maximum number of paths of R passing through any vertex of G. Similarly we define the edge-forwarding index of a network (G,R) as the maximum number of paths of R passing through any edge of G. These parameters might be of interest in different applications concerning communication networks. The forwarding (resp. edge-forwarding) index corresponds to the maximum amount of forwarding done by any node (resp. edge). The edge-forwarding index also corresponds to the maximum load of the network. Therefore it is of interest, for a given graph, to find routings minimizing these indices and we shall define the forwarding (edge-forwarding) index of a graph as the minimum taken over all possible indices of the possible networks.In this paper we give bounds on these forwarding indices, in particular as a function of the connectivity of the graph, and calculate them for products of graphs and for some specific graphs