×

Multicyclic components in a random graph process. (English) Zbl 0766.60014

A random graph process begins with a set of \(n\) isolated vertices. During the evolution of the process edges are added at random by drawing without replacement from the set of all possible edges. Let \(X_ n\) denote the number of components with more than one cycle that are created during the evolution of a random graph process on \(n\geq 4\) vertices. The author studies the characteristic \(X_ n\). In particular, using the method of moments, he proves the weak convergence \(X_ n@>d>>X_ \infty\) as \(n\to\infty\). Explicit expressions for all factorial moments of \(X_ \infty\) are obtained.

MSC:

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

References:

[1] Bollobás, Random Graphs (1985)
[2] Britikov, On the random graph structure near the critical point, Diskret. Mat. 1 pp 121– (1989) · Zbl 0746.05054
[3] Discrete Math. Appl. 1 1991
[4] Flajolet, The first cycles in an evolving graph, Discrete Math. 75 pp 167– (1989) · Zbl 0696.05045
[5] Janson, Poisson convergence and Poisson processes with applications to random graphs, Stoch. Proc. Appl. 26 pp 1– (1987) · Zbl 0633.60070
[6] Janson, A functional limit theorem for random graphs with applications to subgraph count statistics, Random Struct. Alg. 1 pp 15– (1990) · Zbl 0708.05052
[7] S. Janson D. E. Knuth T. Luczak B. Pittel The birth of the giant component
[8] Kallenberg, Random Measures (1983)
[9] Kolchin, On the behaviour of a random graph near a critical point, Theor. Veroyatn. Ee. Primen. 31 pp 503– (1986)
[10] Theory Probab. Its. Appl. 31 pp 439– (1986)
[11] T. Luczak B. Pittel J. C. Wierman The structure of a random graph at the point of the phase transition
[12] Stepanov, On the probability of connectedness of a random graph m( t), Theor. Veroyatn. Ee. Primen. 15 pp 55– (1970) · Zbl 0213.45805
[13] Theory Probab. Its Appl. 15 pp 55– (1970)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.