The Forwarding Indices of Random Graphs
W. Fernandez de la Véga, L. Marquez Gordones · Random Structures and Algorithms · 1992
Abstract 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 by magnified image Where ξ(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 Gp 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 ratio magnified image Tends to 1 in probability as n tends to infinity.