On a random graph evolving by degrees
Starting from an empty graph \(G(0)\) on \(V=\{1,\dots,n\}\), the graph \(G(m)\) is successively obtained from its predecessor \(G(m-1)\) for \(m=1,\dots,n\) by inserting a new edge with conditional probability proportional to the product \((a+d(i))(a+d(j))\), where \(a>0\) is a parameter and \(d(i)\) and \(d(j)\) are the current degrees of any distinct disjoint vertices \(i\) and \(j\). The limiting case with infinite parameter is the Erdős-Rényi graph process. Conditions are given for the existence with high probability of a unique giant component and its asymptotic size. A phase transition window is investigated. Conditions for connectedness with high probability are also given for a multigraph process in which loops and multiple edges are allowed.
scientific article; zbMATH DE number 5653480
scientific article