pith. sign in

arxiv: 1503.09030 · v1 · pith:GKSPHX25new · submitted 2015-03-31 · 🧮 math.CO · cs.DM· math.PR

How does the core sit inside the mantle?

classification 🧮 math.CO cs.DMmath.PR
keywords coredegreegraphrandomappearanceaveragebeenbranching
0
0 comments X
read the original 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 [JCTB 67 (1996) 111--151] determined the threshold $d_k$ 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\geq3$ and any fixed average degree $d=np>d_k$. This generalises prior results on, e.g., the internal structure of the $k$-core.

This paper has not been read by Pith yet.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.