Degeneracy of graph

Question

I'm not really sure I get what the degeneracy of a graph is. My book gives the following definition:

$δ^*(G)=max\{k|$ such that there is a subgraph Η of G: $δ(H)\geq k\}$

Does that imply that $δ^*(G)$ is the supremum of the set containing the minimum vertex degree for all the possible subgraphs of $G$?

And also how do I find the degeneracy of a graph in general?

For example the book gives this excerisise:

Find the value of $δ^*(G) (\bar{K}_{1,q} ∗ \bar{K}_{1,r}),$ $q,r \geq1$

The definition doesn't seem very usefull here..

Also do you know any free online books on introduction to graph theory? I just don't think mine is good enough

Answer 1

Degeneracy arises from the notion that a network or graph with a subgraph of high minimum degree is more robust than a network all of whose subgraphs contain low degree vertices.

For example, we can imagine many situations where a low degree vertex is more vulnerable to failure or attack than a high degree vertex. If a graph has low degeneracy, then repeated attacks on low degree vertices will eventually corrode away the entire graph. If it has high degeneracy, then some "core" of the graph will still remain.

Your definition of the degeneracy as the supremum of the minimum degrees over all subgraphs is correct; this is exactly what it is.

Of course this is useless for computation as there are exponentially many subgraphs, but fortunately it turns out that degeneracy is easy to compute via a greedy algorithm as follows:

Until $G$ is empty, do the following:

1. Write down the minimum degree of $G$
2. Identify a vertex $v$ of this minimum degree
3. Delete $v$ and its incident edges from $G$

Then the degeneracy is the maximum of the values you have written down.

Proof

Suppose that the algorithm returns a value $k$, and the true degeneracy of the graph is $k'$.

[$k$ cannot be too big] Show that $k \leqslant k'$:

Consider the graph at the moment in the algorithm where $k$ is written down as the minimum degree. Then the subgraph of $G$ at that point has minimum degree $k$, and so $k \leqslant k'$.

[$k$ cannot be too small] Show that $k' \leqslant k$:

Pick your favourite subgraph of minimum degree $k'$, and consider the moment in the algorithm at which the first vertex of this subgraph is removed. As all the other vertices of the subgraph are still there, the minimum degree is at least $k'$ and so some number at least $k'$ is written down.