An example of graph limits of growing sequences of random graphs

In this paper, we consider a class of growing random graphs obtained by creating vertices sequentially one by one. At each step, we uniformly choose the neighbors of the newly created vertex; its degree is a random variable with a fixed but arbitrary distribution, depending on the number of existing vertices. Examples from this class turn out to be the Erdős–Rényi random graph, a natural random threshold graph, etc. By working with the notion of graph limits, we define a kernel which, under certain conditions, is the limit of the growing random graph. Moreover, for a subclass of models, the growing graph on any given $n$ vertices has the same distribution as the random graph with n vertices that the kernel defines. The motivation stems from a model of graph growth whose attachment mechanism does not require information about properties of the graph at each iteration.

2010 Mathematics Subject Classification

05C80

Full Text (PDF format)

Published 16 May 2013