The phase transition of the minimum degree random multigraph process
By Mihyun Kang and Taral Guldahl SeierstadRandom Structures and Algorithms, 31 (2007): 330-353
Abstract
We study the phase transition of the minimum degree multi-graph process. We prove that for a constant hg ~ 0.8607, with probability tending to 1 as n -> infty, the graph consists of small components on O(log n) vertices when the number of edges of a graph generated so far is smaller than hg n, the largest component has order roughly n2/3 when the number of edges added is exactly hg n, and the graph consists of one giant component on &Theta(n) vertices and small components on O(log n) vertices when the number of edges added is larger than hg n.
Download
- pdf - minran.pdf
- ps - minran.ps
