### Abstract

The k-core of a graph is the largest subgraph with minimum degree at least k. For the Erdos-Rényi random graph G(n, m) on n vertives, with m edges, it is known that a giant 2-core grows simultaneously with a giant component, that is, when m is close to n/2. We show that for k ≥ 3, with high probability, a giant k-core appears suddenly when m reaches c_{k}n/2; here c_{k} = min_{λ>0} λ/π_{k}(λ) and π_{k}(λ) = P{Poisson(λ)≥k-1}. In particular, c_{3}≈3.35. We also demonstrate that, unlike the 2-core, when a k-core appears for the first time it is very likely to be giant, of size ≈p_{k}(λ_{k})n. Here λ_{k} is the minimum point of λ/π_{k}(λ) and p_{k}(λ_{k}) = P{Poisson(λ_{k})≥k}. For k = 3, for instance, the newborn 3-core contains about 0.27n vertices. Our proofs are based on the probabilistic analysis of an edge deletion algorithm that always find a k-core if the graph has one.

Original language | English |
---|---|

Pages (from-to) | 111-151 |

Number of pages | 41 |

Journal | Journal of Combinatorial Theory, Series B |

Volume | 67 |

Issue number | 1 |

DOIs | |

Publication status | Published - 1996 |

Externally published | Yes |

## Cite this

*Journal of Combinatorial Theory, Series B*,

*67*(1), 111-151. https://doi.org/10.1006/jctb.1996.0036