3
$\begingroup$

A k-core of a graph is the maximal subgraph with minimal degree k. For example, the 2-core would emerge by subsequently deleting degree-1 vertices of a graph.

I've seen a lot of work on existence of nontrivial k-cores of a random graph, and some on the number of vertices/edges in the k-core of a random graph. I would like to know if, for specific graph models, there are known theorems describing the distribution of the k-core, e.g. when the original graph is

Erdös Renyi or Configuration model/given degree sequence

will the resulting 2-core be distributed as ER/configuration?

A quick comment on previous works: Janson/Luczak published "Asymptotic normality of the k-Core in random graphs" as well as "A simple solution to the k-core problem". Cooper/Frieze/Lubetzky in their paper "Cover time of a random graph with a degree sequence II: Allowing vertices of degree two" calculated the distribution of the kernel in a configuration model with minimum degree 2, but I don't think their method works for the 2-core.

$\endgroup$

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.