Journal article icon

Journal article

Slow emergence of the giant component in the growing m-out graph

Abstract:

Let H m(n) be a random graph on n vertices, grown by adding vertices one at a time, joining each new vertex to a uniformly chosen set of m earlier vertices. If edges of H m(n) are deleted independently, each being retained with probability p, then there is a "phase transition". There is a certain critical value p c of p such that, with high probability, a component of order θ(n) remains as n → ∞ if and only if p > p c. Among other results, we obtain the exact value of p c, which depends on...

Expand abstract
Publication status:
Published

Actions


Access Document


Publisher copy:
10.1002/rsa.20060

Authors


Journal:
RANDOM STRUCTURES and ALGORITHMS
Volume:
27
Issue:
1
Pages:
1-24
Publication date:
2005-08-05
DOI:
EISSN:
1098-2418
ISSN:
1042-9832
URN:
uuid:4d08e888-412a-44da-9f89-306dd688341a
Source identifiers:
4389
Local pid:
pubs:4389
Language:
English

Terms of use


Metrics


Views and Downloads






If you are the owner of this record, you can report an update to it here: Report update to this record

TO TOP