A critical point for random graphs with a given degree sequence - Molloy - 1995 - Random Structures & Algorithms - Wiley Online Library
Volume 6, Issue 2‐3
Article

A critical point for random graphs with a given degree sequence

Michael Molloy

Department of Mathematics, Carnegie Mellon University, Pittsburgh, PA 15213

Search for more papers by this author
Bruce Reed

Equipe Combinatoire, CNRS, Universite Pierre et Marie Curie, Paris, France

Search for more papers by this author
First published: March ‐ May 1995
Citations: 1,188
"Library Links”

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.

The full text of this article hosted at iucr.org is unavailable due to technical difficulties.