The diameter of sparse random graphs
We derive an expression of the form c In n+o(In n) for the diameter of a sparse random Graph with a specified degree sequence. The result holds asymptotically almost surely, assuming that certain convergence and supercriticality conditions are met, and is applicable to the classical random graph G(n,p) with np = Theta (1) + 1, as well as certain random power law graphs. (C) 2007 Wiley Periodicals, Inc.
diameter random graph degree sequence configuration model