A general critical condition for the emergence of a giant component in random graphs with given degrees - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Communication Dans Un Congrès Année : 2009

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

Résumé

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.
Fichier non déposé

Dates et versions

hal-00795285 , version 1 (27-02-2013)

Identifiants

  • HAL Id : hal-00795285 , version 1

Citer

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⟩
133 Consultations
0 Téléchargements

Partager

Gmail Facebook X LinkedIn More