Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
4651937 | Electronic Notes in Discrete Mathematics | 2015 | 8 Pages |
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