Article ID Journal Published Year Pages File Type
4651937 Electronic Notes in Discrete Mathematics 2015 8 Pages PDF
Abstract

The k-core, defined as the largest subgraph of minimum degree k, of the random graph G(n,p) has been studied extensively. In a landmark paper Pittel, Wormald and Spencer [Journal of Combinatorial Theory, Series B 67 (1996) 111–151] determined the threshold dk for the appearance of an extensive k-core. Here we derive a multi-type Galton-Watson branching process that describes precisely how the k-core is “embedded” into the random graph for any k≥3 and any fixed average degree d=np>dk. This generalises prior results on, e.g., the internal structure of the k-core.

Related Topics
Physical Sciences and Engineering Mathematics Discrete Mathematics and Combinatorics