Exactly solvable model of a coalescing random graph

An initially empty (no edges) graph of order $M$ evolves by randomly adding one edge at a time. This edge connects either two linked components and forms a new component of larger order (coalescence of graphs) or increases (by one) the number of edges in a given linked component (cycling). Assuming that the vertices of the graph have a finite valence (the number of edges connected with a given vertex is limited) the kinetic equation for the distribution of linked components of the graph over their orders and valences is formulated and solved by applying the generating function method. The evolution process is shown to reveal a phase transition: the emergence of a giant linked component whose order is comparable to the total order of the graph. The kinetics of growth of this component is studied for arbitrary initial conditions. Found are the time dependences of the average order and the valence of the giant component. The distribution over orders and valences of the linked components of the graph is derived for an initially empty graph comprising $M$ bare polyvalent vertices.

Figure 1

Evolution of a random graph. Shown is a fragment of the random graph comprising two linked component of orders 6 and 5. Each vertex has the valence 3. Extra edge $cd$ (dash line) appearing in the the graph can thus connect the vertices $b$ and $c$, but it cannot connect the vertices $a$ and $d$, because they have not free valences. Neither extra edges $bd$ or $ac$ are possible.

Figure 2

The time dependence of total order (solid line) and total valence (dash line) of the giant component for $s=3$.

Figure 3

Same as in Fig. 2 for $s=4$.