The Diameter of Sparse Random Graphs
Random Structures and Algorithms · 2007
Abstract We derive an expression of the form c ln n \\Sigma o(ln n) for the diameter of a sparse random graph with a specified degree sequence. The result holds a.a.s., assuming certain convergence and supercriticality conditions are met. The proof is constructive and yields a method for computing the constant c. For the random graph G n;p with np = \\Theta (1) + 1, we solve for c in closed form.