Cores, shell indices and the degeneracy of a graph limit

Johannes Rauh

Contact the author: Please use for correspondence this email.
Submission date: 16. May. 2018
Pages: 13
Bibtex
MSC-Numbers: 05CXX
Keywords and phrases: graph limit, shell index, graph core, graph degeneracy
Download full preprint: PDF (365 kB)
Link to arXiv: See the arXiv entry of this preprint.

Abstract:
The k-core of a graph is the maximal subgraph in which every node has degree at least k, the shell index of a node is the largest k such that the k-core contains the node, and the degeneracy of a graph is the largest shell index of any node. After a suitable normalization, these three concepts generalize to limits of dense graphs (also called graphons). In particular, the degeneracy is continuous with respect to the cut metric.