zbMATH — the first resource for mathematics

The maximum degree of the Barabási-Albert random tree. (English) Zbl 1078.05077
Let \(S(n)= 2n+ (n+1)\beta\), for a fixed parameter \(\beta> -1\). Consider a random tree constructed as follows. At the first step there is a single edge joining vertices labelled 0 and 1. At step \(n +1\) a vertex of degree \(k\) is chosen with probability \((k+ \beta)/S(n)\) from the existing tree and joined to a new vertex labelled \(n+ 1\). The author uses martingale methods to show that the maximum degree \(M_n\) of the tree after the \(n\)th step, divided by \(n^{1/(2+\beta)}\), converges almost surely to a positive random variable as \(n\to\infty\).

05C80 Random graphs (graph-theoretic aspects)
05C05 Trees
60C05 Combinatorial probability
Full Text: DOI