A phase transition for the diameter of the configuration model

R.W. Hofstad, van der, G. Hooghiemstra, D. Znamenski

Research output: Contribution to journalArticleAcademicpeer-review

10 Citations (Scopus)

Abstract

In this paper, 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 t of the degrees satisfies t ¿ (2, 3). Indeed, we show that for t > 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 t ¿ (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.
Original languageEnglish
Pages (from-to)113-128
JournalInternet Mathematics
Volume4
Issue number1
Publication statusPublished - 2007

Fingerprint Dive into the research topics of 'A phase transition for the diameter of the configuration model'. Together they form a unique fingerprint.

Cite this