# 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$$.

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