On the number of vertices of given degree in a random graph

✍ Scribed by Zbigniew Palka

• Publisher: John Wiley and Sons
• Year: 1984
• Tongue: English
• Weight: 115 KB
• Volume: 8
• Category: Article
• ISSN: 0364-9024
• DOI: 10.1002/jgt.3190080119

✦ Synopsis

This note can be treated a s a supplement to a paper written by Bollobas which was devoted to the vertices of a given degree in a random graph. We determine some values of the edge probability p for which the number of vertices of a given degree of a random graph G E ?An, p) asymptotically has a normal distribution.

Here we shall be concerned with the discrete probability space %(n, p ) consisting of the undirected simple graphs with a fixed set of n labeled vertices in which each of ("3 possible edges occurs with the same probability p (0 < p < 1) independently of all other edges. Let x k = &(G) be the number of vertices of degree k of a graph G E %(n, p). Then the expectation of Xk(G) is Adn) = nb(k; n -I , p ) where b(k;n,p ) = (;.

In his paper BollobAs [I] proved, among other results, that if ~n-"'

Ak(n) < 03, then X, asymptotically has the Poisson distribution with mean Ak(n). In addition, if lim A,(n) = m then for every fixed t almost every graph has at least t vertices of degree k.

In this note we focus our attention on the latter case and determine those values of the edge probability p for which the random variable Xk =