Mathematics – Combinatorics
Scientific paper
2005-11-03
Combinatorics, Probability and Computing 17 (2008) 111--136.
Mathematics
Combinatorics
30 pages, 1 figure. Minor revisions. To appear in Combinatorics, Probability and Computing
Scientific paper
10.1017/S0963548307008589
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 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 at least 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 \epsilon above the threshold. In contrast to $G(n,\lambda/n)$, this fraction tends to 0 as \epsilon tends to 0.
No associations
LandOfFree
The k-core and branching processes does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with The k-core and branching processes, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and The k-core and branching processes will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-483137