Loading...
Loading...

Go to the content (press return)

How to determine if a random graph with a fixed degree sequence has a giant component

Author
Joos, F.; Perarnau-Llobet, G.; Rautenbach, D.; Reed, B.
Type of activity
Journal article
Journal
Probability theory and related fields
Date of publication
2017-01-26
Volume
170
Number
1-2
First page
263
Last page
310
DOI
10.1007/s00440-017-0757-1
Repository
http://hdl.handle.net/2117/133718 Open in new window
https://arxiv.org/abs/1601.03714 Open in new window
Abstract
For a fixed degree sequence D=(d1,…,dn) , let G(D) be a uniformly chosen (simple) graph on {1,…,n} where the vertex i has degree di . In this paper we determine whether G(D) has a giant component with high probability, essentially imposing no conditions on D . We simply insist that the sum of the degrees in D which are not 2 is at least ¿(n) for some function ¿ going to infinity with n. This is a relatively minor technical condition, and when D does not satisfy it, both the probability tha...
Citation
Joos, F. [et al.]. How to determine if a random graph with a fixed degree sequence has a giant component. "Probability theory and related fields", 26 Gener 2017, vol. 170, núm. 1-2, p. 263-310.
Group of research
GAPCOMB - Geometric, Algebraic and Probabilistic Combinatorics

Participants

Attachments