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

Nikolaos Fountoulakis 1 Bruce Reed 2, 3
3 MASCOTTE - Algorithms, simulation, combinatorics and optimization for telecommunications
CRISAM - Inria Sophia Antipolis - Méditerranée , 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.
Type de document :
Communication dans un congrès
European Conference on Combinatorics, Graph Theory and Applications (Eurocomb 2009), 2009, Bordeaux, France. 34, pp.639―645, 2009, Electronic Notes on Discrete Mathematics
Liste complète des métadonnées

https://hal.inria.fr/hal-00795285
Contributeur : Alain Monteil <>
Soumis le : mercredi 27 février 2013 - 17:07:04
Dernière modification le : mercredi 14 décembre 2016 - 01:06:35

Identifiants

  • 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. 34, pp.639―645, 2009, Electronic Notes on Discrete Mathematics. <hal-00795285>

Partager

Métriques

Consultations de la notice

146