Phase transition of the minimum degree random multigraph process
We study the phase transition of the minimum degree multigraph process. We prove that for a constant h(g) approximate to 0.8607, with probability tending to 1 as n -> infinity, the graph consists of small components on 0(log n) vertices when the number of edges of a graph generated so far is smaller than h(g)n, the largest component has order roughly n(2/3) when the number of edges added is exactly h(g)n, and the graph consists of one giant component on Theta (n) vertices and small components on 0(log n) vertices when the number of edges added is larger than h(g)n. (C) 2007 Wiley Periodicals, Inc.
phase transition random graph random graph process branching process