×

A phase transition for the diameter of the configuration model. (English) Zbl 1167.05048

Summary: We study the configuration model (CM) with independent and identically-distributed (i.i.d.) degrees. We establish a phase transition for the diameter when the power-law exponent \(\tau\) of the degrees satisfies \(\tau \in (2,3)\). Indeed, we show that for \(\tau > 2\) and when vertices with degree 1 or 2 are present with positive probability, the diameter of the random graph is, with high probability, bounded from below by a constant times the logarithm of the size of the graph. On the other hand, assuming that all degrees are 3 or more, we show that, for \(\tau\in (2,3)\), the diameter of the graph is, with high probability, bounded from above by a constant times the \(\log\log\) of the size of the graph.

MSC:

05C80 Random graphs (graph-theoretic aspects)
05C12 Distance in graphs
Full Text: DOI