Combinatorics, Probability and Computing



The Size of the Giant Component of a Random Graph with a Given Degree Sequence


MICHAEL MOLLOY a1 and BRUCE REED a2
a1 Department of Computer Science, University of Toronto, Toronto, Canada (e-mail: molloy@cs.toronto.edu)
a2 Equipe Combinatoire, CNRS, Université Pierre et Marie Curie, Paris, France (e-mail: reed@ecp6.jussieu.fr)

Abstract

Given a sequence of nonnegative real numbers λ0, λ1, … that sum to 1, we consider a random graph having approximately λin vertices of degree i. In [12] the authors essentially show that if [sum L: summation operator]i(i−2)λi>0 then the graph a.s. has a giant component, while if [sum L: summation operator]i(i−2)λi<0 then a.s. all components in the graph are small. In this paper we analyse the size of the giant component in the former case, and the structure of the graph formed by deleting that component. We determine ε, λ′0, λ′1 … such that a.s. the giant component, C, has εn+o(n) vertices, and the structure of the graph remaining after deleting C is basically that of a random graph with n′=n−[mid R:]C[mid R:] vertices, and with λ′in′ of them of degree i.

(Received November 22 1996)
(Revised May 29 1997)