A critical point for random graphs with a given degree sequence
- 1 March 1995
- journal article
- research article
- Published by Wiley in Random Structures & Algorithms
- Vol. 6 (2-3), 161-180
- https://doi.org/10.1002/rsa.3240060204
Abstract
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 Gn,p,Gn.M, and other well‐known models of random graphs. There are also applications related to the chromatic number of sparse random graphs.Keywords
This publication has 9 references indexed in Scilit:
- Almost all cubic graphs are HamiltonianRandom Structures & Algorithms, 1992
- Almost all graphs with 1.44n edges are 3‐colorableRandom Structures & Algorithms, 1991
- Component behavior near the critical point of the random graph processRandom Structures & Algorithms, 1990
- On the method of bounded differencesPublished by Cambridge University Press (CUP) ,1989
- The first cycles in an evolving graphDiscrete Mathematics, 1989
- The chromatic number of random graphs at the double-jump thresholdCombinatorica, 1989
- On Matchings and Hamiltonian Cycles in Random GraphsPublished by Elsevier ,1985
- The asymptotic number of labeled graphs with given degree sequencesJournal of Combinatorial Theory, Series A, 1978
- Weighted sums of certain dependent random variablesTohoku Mathematical Journal, 1967