Skip to Main content Skip to Navigation
Conference papers

A general critical condition for the emergence of a giant component in random graphs with given degrees

Nikolaos Fountoulakis 1 Bruce Reed 2
2 MASCOTTE - Algorithms, simulation, combinatorics and optimization for telecommunications
CRISAM - Inria Sophia Antipolis - Méditerranée , Laboratoire I3S - COMRED - COMmunications, Réseaux, systèmes Embarqués et Distribués
Abstract : In this contribution, we investigate the giant component problem in random graphs with a given degree sequence. We generalize the critical condition of Molloy and Reed [Molloy, M., and B. Reed, A critical point for random graphs with given degree sequence, Random Structures Algorithms 6 (1995), 161-179], which determines the existence of a giant component in such a random graph, in order to include degree sequences with heavy tails. We show that the quantity which determines the existence of a giant component is the value of the smallest fixed point inside the interval [0, 1] of the generating function F(s)=∑i⩾1δisi−1, where δi is the asymptotic proportion of the total degree contained in vertices of degree i. Moreover, we show that this quantity also determines the existence of a core (i.e., the maximal subgraph of minimum degree at least 2) that has linear total degree.
Complete list of metadata

https://hal.inria.fr/hal-00795285
Contributor : Alain Monteil <>
Submitted on : Wednesday, February 27, 2013 - 5:07:04 PM
Last modification on : Monday, October 12, 2020 - 10:30:26 AM

Identifiers

  • HAL Id : hal-00795285, version 1

Collections

Citation

Nikolaos Fountoulakis, Bruce Reed. A general critical condition for the emergence of a giant component in random graphs with given degrees. European Conference on Combinatorics, Graph Theory and Applications (Eurocomb 2009), 2009, Bordeaux, France. pp.639―645. ⟨hal-00795285⟩

Share

Metrics

Record views

283