Journal article icon

Journal article

The k-core and branching processes

Abstract:

The k-core of a graph G is the maximal subgraph of G having minimum degree at least k. In 1996, Pittel, Spencer and Wormald found the threshold $\lambda_c$ for the emergence of a non-trivial k-core in the random graph $G(n,\lambda/n)$, and the asymptotic size of the k-core above the threshold. We give a new proof of this result using a local coupling of the graph to a suitable branching process. This proof extends to a general model of inhomogeneous random graphs with independence between the...

Expand abstract
Publication status:
Published

Actions


Access Document


Publisher copy:
10.1017/S0963548307008589

Authors


Journal:
Probability and Computing
Volume:
17
Issue:
1
Pages:
111-136
Publication date:
2005-11-03
DOI:
EISSN:
1469-2163
ISSN:
0963-5483
Source identifiers:
16715
Language:
English
Keywords:
Pubs id:
pubs:16715
UUID:
uuid:0a7f0079-718e-4e01-88f7-2f9afe3fcdda
Local pid:
pubs:16715
Deposit date:
2012-12-19

Terms of use


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