The Forwarding Indices of Random Graphs

A routing R of a graph G is a set of n(n − 1) elementary paths R(u, v) specified for all ordered pairs ( u, v ) of vertices of G . The vertex‐forwarding index ξ( G ) of G , is defined byWhere ξ( G, R ) is the maximum number of paths of the routing R passing through any vertex of G and the minimum is taken over all the routings of G . Let G p denote the random graph on n vertices with edge probability p and let m = np . It is proved among other things that, under natural growth conditions on the function p = p(n) , the ratioTends to 1 in probability as n tends to infinity.