2005/11/30 by Oliver Riordan
Mathematics · Physics and Astronomy · #Complex Network Analysis Techniques #Limits and Structures in Graph Theory #Stochastic processes and statistical mechanics #math.CO #math.PR #msc:05C80
paper · pdf · doi:10.1017/s0963548307008589
published as Combinatorics, Probability and Computing 17 (2008) 111--136. · 30 pages, 1 figure. Minor revisions. To appear in Combinatorics, Probability and Computing
arxiv created 2007/02/12 · openalex publication_date 2007/06/27 · arxiv updated 2009/12/01 · openalex created_date 2016/06/24 · openalex updated_date 2026/07/28
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 λ c for the emergence of a non-trivial k -core in the random graph G ( n , λ/ 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 edges. As an example, we study the k -core in a certain power-law or ‘scale-free’ graph with a parameter c controlling the overall density of edges. For each k ≥ 3, we find the threshold value of c at which the k -core emerges, and the fraction of vertices in the k -core when c is ϵ above the threshold. In contrast to G ( n , λ/ n ), this fraction tends to 0 as ϵ→0.