Markov branching in the vertex splitting model

Abstract

We study a special case of the vertex splitting model which is a recent model of randomly growing trees. For any finite maximum vertex degree $D$, we find a one parameter model, with parameter $α\in [0,1]$ which has a so--called Markov branching property. When $D=\infty$ we find a two parameter model with an additional parameter $γ\in [0,1]$ which also has this feature. In the case $D = 3$, the model bears resemblance to Ford's $α$--model of phylogenetic trees and when $D=\infty$ it is similar to its generalization, the $αγ$--model. For $α= 0$, the model reduces to the well known model of preferential attachment. In the case $α> 0$, we prove convergence of the finite volume probability measures, generated by the growth rules, to a measure on infinite trees which is concentrated on the set of trees with a single spine. We show that the annealed Hausdorff dimension with respect to the infinite volume measure is $1/α$. When $γ= 0$ the model reduces to a model of growing caterpillar graphs in which case we prove that the Hausdorff dimension is almost surely $1/α$ and that the spectral dimension is almost surely $2/(1+α)$. We comment briefly on the distribution of vertex degrees and correlations between degrees of neighbouring vertices.

30 pages,7 figures