The Diameter of Sparse Random Graphs

We consider the diameter of a random graph G(n, p) for various ranges of p close to the phase transition point for connectivity. For a disconnected graph G, we use the convention that the diameter of G is the maximum diameter of its connected components. We show that almost surely the diameter of random graph G(n, p) is close to if np → ∞. Moreover if , then the diameter of G(n, p) is concentrated on two values. In general, if , the diameter is concentrated on at most 21/c₀ + 4 values. We also proved that the diameter of G(n, p) is almost surely equal to the diameter of its giant component if np > 3.6.