Premium
The Forwarding Indices of Random Graphs
Author(s) -
Fernandez de la Vega W.,
Gordones L. Marquez
Publication year - 1992
Publication title -
random structures and algorithms
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.314
H-Index - 69
eISSN - 1098-2418
pISSN - 1042-9832
DOI - 10.1002/rsa.3240030108
Subject(s) - combinatorics , vertex (graph theory) , mathematics , random graph , graph , discrete mathematics
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 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.