= k-core of a graph
{title2=$C_k(G)$}
For a nonnegative <integer> $k$, the <k-core of a graph> is the unique maximum by <set inclusion> <induced subgraph> in which every <degree of a vertex> is at least $k$, allowing the empty <graph>. Repeatedly delete <vertices> whose current <degree of a vertex> is less than $k$. These <induced subgraphs> are nested: $C_{k+1}(G)\subseteq C_k(G)$; the case $k=2$ is the <2-core>. In their 2003 preprint, <Vladimir Batagelj> and <Matjaž Zaveršnik> give an <algorithm> for the entire core decomposition, using degree buckets and constant-time position updates. Their general bound is $O(|V|+|E|)$; the title's $O(m)$ form applies to <connected graphs> with at least two <vertices>, where $m=|E|\geq|V|-1$. <An O(m) Algorithm for Cores Decomposition of Networks by Vladimir Batagelj and Matjaž Zaveršnik>[Batagelj and Zaveršnik, An O(m) Algorithm for Cores Decomposition of Networks, §§2–4.1, especially Algorithm 1 and the general O(max(m,n)) bound]{ref}
Back to article page
