Premium
A critical point for random graphs with a given degree sequence
Author(s) -
Molloy Michael,
Reed Bruce
Publication year - 1995
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/rsa.3240060204
Subject(s) - combinatorics , random graph , mathematics , degree (music) , indifference graph , random regular graph , discrete mathematics , giant component , chordal graph , sequence (biology) , trapezoid graph , clique sum , 1 planar graph , graph , physics , biology , acoustics , genetics
Given a sequence of nonnegative real numbers λ 0 , λ 1 … which sum to 1, we consider random graphs having approximately λ i n vertices of degree i. Essentially, we show that if Σ i(i ‐ 2)λ i > 0, then such graphs almost surely have a giant component, while if Σ i ( i ‐ 2)λ. < 0, then almost surely all components in such graphs are small. We can apply these results to G n,p ,G n.M , and other well‐known models of random graphs. There are also applications related to the chromatic number of sparse random graphs.