Premium
Growth of components in random graphs
Author(s) -
Janson Svante
Publication year - 2000
Publication title -
random structures and algorithms
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.314
H-Index - 69
eISSN - 1098-2418
pISSN - 1042-9832
DOI - 10.1002/1098-2418(200010/12)17:3/4<343::aid-rsa8>3.0.co;2-d
Subject(s) - struct , random graph , mathematics , wright , combinatorics , component (thermodynamics) , graph , discrete mathematics , computer science , physics , thermodynamics , programming language
The creation and growth of components of a given complexity in a random graph process are studied. In particular, the expected number and total size of all such components is found. It follows that the largest l ‐component during the process is O p ( n 2/3 ) for any given l . The results also yield a new proof of the asymptotic behaviour of Wright's coefficients. © 2000 John Wiley & Sons, Inc. Random Struct. Alg., 17: 343–356, 2000