A critical point for random graphs with a given degree sequence
Random Structures and AlgorithmsPublished 1 March 1995
Michael Molloy, Bruce Reed
Citations2,401
SJR quartileQ1
SJR score1.05
SNIP1.22
Generate an AI Snapshot to get a quick, structured summary of this paper.
Study Snapshot
ObjectiveStudy objective
MethodsResearch methodology
PopulationPopulation studied
Sample sizeSample sizes
OutcomesStudy outcomes here
ResultsStudy results comes here
LimitationsResearch study limitations comes here
A concise AI-generated summary of the paper will appear here once you click Generate AI Snapshot.
TL;DR
It is shown that if Σ i(i - 2)λi > 0, then such graphs almost surely have a giant component, while if λ0, λ1… which sum to 1, then almost surely all components in such graphs are small.
Abstract
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 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.
Keywords
Computer ScienceMathematics
Journal of the Franklin InstituteAn introduction to probability theory and its applications
29,966 Citations1958
Cambridge University Press eBooksOn the method of bounded differences
1,428 Citations1989Colin McDiarmid
Journal of Combinatorial Theory Series AThe asymptotic number of labeled graphs with given degree sequences
996 Citations1978Edward A. Bender, E. Rodney Canfield
Asymptotics are obtained for the number of n × n symmetric non-negative integer matrices subject to the following constraints: each row sum is specified and bounded, and a specified “sparse” set of entries must be zero.
Random Structures and AlgorithmsThe birth of the giant component
402 Citations1993Svante Janson, Donald E. Knuth +2 more
A “uniform” model of random graphs, which allows self-loops and multiple edges, is shown to lead to formulas that are substanitially simpler than the analogous formulas for the classical random graphs of Erdos and Renyi.
Random Structures and AlgorithmsComponent behavior near the critical point of the random graph process
231 Citations1990Tomasz Łuczak
It is shown that, with probability 1 o(l), when M ( n ) = n12 + s, s 3 C 2 + -a, then during a random graph process in some step M’ > M a “new” largest component will emerge, and when s3n-*+m, the largest component of G(n, M) remains largest until the very end of the process.
Random Structures and AlgorithmsAlmost all regular graphs are hamiltonian
213 Citations1994Robert W. Robinson, N. C. Wormald
This result is used to show that almost all r‐regular graphs are hamiltonian for any fixed r ⩾ 3, by an analysis of the distribution of 1‐factors in random regular graphs.
North-Holland mathematics studiesRandom Graphs of Small Order
176 Citations1985Béla Bollobás, Andrew Thomason
A large number of tables displaying the parameters of various randomly chosen graphs of small order are presented, many of which are obtained by substantial use of a computer.
Random Structures and AlgorithmsAlmost all cubic graphs are Hamiltonian
159 Citations1992Robert W. Robinson, N. C. Wormald
In a previous article the authors showed that at least 98.4% of large labelled cubic graphs are hamiltonian in the limit by asymptotic analysis of the variance of the number of Hamilton cycles with respect to populations of cubic graphs with fixed numbers of short odd cycles.
Bulletin of the Australian Mathematical SocietySome problems in the enumeration of labelled graphs
131 Citations1980Nicholas Wormald
North-Holland mathematics studiesOn Matchings and Hamiltonian Cycles in Random Graphs
109 Citations1985Béla Bollobás, Alan Frieze
Discrete MathematicsThe first cycles in an evolving graph
98 Citations1989Philippe Flajolet, Donald E. Knuth +1 more
The probability is √2/3 + O(n −1/3 ) that the graph has no components with more than one cycle at the moment when the number of edges passes ½ n and the results can be proved with analytical methods based on combinatorial enumeration with multivariate generating functions, followed by contour integration to derive asymptotic formulas for the quantities of interest.
Random Structures and AlgorithmsAlmost all graphs with 1.44n edges are 3‐colorable
54 Citations1991Vašek Chvátal
It is proved that almost all graphs with n vertices and 1.44 n edges contain no subgraph with minimum degree at least three, and hence are 3-colorable.
COMBINATORICAThe chromatic number of random graphs at the double-jump threshold
21 Citations1989Tomasz Łuczak, John C. Wierman
It is proved that whenp=1/n, almost all graphs do not contain a cycle with a diagonal edge, contradicting Theorem 8a of Erdös and Rényi (1960).