# zbMATH — the first resource for mathematics

Randomised reproducing graphs. (English) Zbl 1244.05211
Summary: We introduce a model for a growing random graph based on simultaneous reproduction of the vertices. The model can be thought of as a generalisation of the reproducing graphs of Southwell and Cannings and Bonato et al to allow for a random element, and there are three parameters, $$\alpha, \beta$$ and $$\gamma$$, which are the probabilities of edges appearing between different types of vertices.
We show that as the probabilities associated with the model vary there are a number of phase transitions, in particular concerning the degree sequence. If $$(1+\alpha)(1+\gamma)<1$$ then the degree distribution converges to a stationary distribution, which in most cases has an approximately power law tail with an index which depends on $$\alpha$$ and $$\gamma$$. If $$(1+\alpha)(1+\gamma)>1$$ then the degree of a typical vertex grows to infinity, and the proportion of vertices having any fixed degree $$d$$ tends to zero. We also give some results on the number of edges and on the spectral gap.

##### MSC:
 05C82 Small world graphs, complex networks (graph-theoretic aspects) 05C80 Random graphs (graph-theoretic aspects) 60G99 Stochastic processes 60J10 Markov chains (discrete-time Markov processes on discrete state spaces)
Full Text: