Diameter in ultra-small scale-free random graphs.

It is well known that many random graphs with infinite variance degrees are ultra-small. More precisely, for configuration models and preferential attachment models where the proportion of vertices of degree at least k is approximately k (-(τ - 1)) with τ ∈ (2,3), typical distances between pairs of vertices in a graph of size n are asymptotic to 2/2 and 4/2 , respectively. In this paper, we investigate the behavior of the diameter in such models. We show that the diameter is of order loglogn precisely when the minimal forward degree d (fwd) of vertices is at least 2. We identify the exact constant, which equals that of the typical distances plus 2/logdfwd . Interestingly, the proof for both models follows identical steps, even though the models are quite different in nature.