The connectivity threshold for the min-degree random graph process
By Mihyun Kang, Youngmee Koh, Tomasz Łuczak, and Sangwook ReeRandom Structures and Algorithms, 29 (2006), 105-120
Abstract
Let {G(n,M)}M > = 0 denote a min-degree random multigraph process in which G(n,M+1) is obtained from G(n,M) by connecting a randomly chosen vertex of a minimum degree with another vertex of the multigraph. We study the probability that the random mutligraph G(n,M) is connected.
Download
- ps.gz - mindeg.ps.gz
