A kinetic approach to the random \(f\)-graph process. Paths, cycles and components (Q1917316)

This paper describes a model of random graphs with bounded degree, called random \(f\)-graphs. At each step an edge is added to the graph provided its insertion does not cause the degree of any vertex to exceed \(f\). The edge that is added is picked uniformly at random from among all edges that can be added without violating the degree restriction. In the case \(f=n-1\), we get the usual random graph model. The authors note that little is known about such graphs. In this paper, the authors study the number of paths, cycles and components of a random 2-graph. The key technique is to model the underlying process with a series of differential equations. The authors also provide the degree distribution of \(f\)-graphs for all \(f\geq 2\).