Dynamics of Random Graphs with Bounded Degrees

We investigate the dynamic formation of regular random graphs. In our model, we pick a pair of nodes at random and connect them with a link if both of their degrees are smaller than $d$. Starting with a set of isolated nodes, we repeat this linking step until a regular random graph, where all nodes have degree $d$, forms. We view this process as a multivariate aggregation process, and formally solve the evolution equations using the Hamilton-Jacobi formalism. We calculate the nontrivial percolation thresholds for the emergence of the giant component when $d\geq 3$. Also, we estimate the number of steps until the giant component spans the entire system and the total number of steps until the regular random graph forms. These quantities are non self-averaging, namely, they fluctuate from realization to realization even in the thermodynamic limit.