A kinetic approach to the random f-graph process. Paths, cycles and components Original Research Article

Starting with n labeled vertices and no edges, introduce edges, one at a time, so as to obtain a sequence of graphs each having no vertex of degree greater than f. The latter are called f-graphs. At each step the edge to be added is selected with equal probability from among those edges whose addition would not violate the f-degree restriction. This procedure is called the Random f-Graph Process (Rf-GP) of order n. Here we determine some properties of the numbers of paths, cycles and components for the R2-GP and provide the vertex degree distribution for all f⩾ 2.