Degeneracy (graph theory)

In graph theory, a k-degenerate graph is an undirected graph in which every subgraph has a vertex of degree at most k: that is, some vertex in the subgraph touches k or fewer of the subgraph's edges. The degeneracy of a graph is the smallest value of k for which it is k-degenerate. The degeneracy of a graph is a measure of how sparse it is, and is within a constant factor of other sparsity measures such as the arboricity of a graph.

Degeneracy is also known as the k-core number,width, and linkage, and is essentially the same as the coloring number or Szekeres-Wilf number (named after Szekeres and Wilf (1968)). k-degenerate graphs have also been called k-inductive graphs. The degeneracy of a graph may be computed in linear time by an algorithm that repeatedly removes minimum-degree vertices. The connected components that are left after all vertices of degree less than k have been removed are called the k-cores of the graph and the degeneracy of a graph is the largest value k such that it has a k-core.

Every forest has either an isolated vertex (incident to no edges) or a leaf vertex (incident to exactly one edge); therefore, trees and forests are 1-degenerate graphs.

Every finite planar graph has a vertex of degree five or less; therefore, every planar graph is 5-degenerate, and the degeneracy of any planar graph is at most five. Similarly, every outerplanar graph has degeneracy at least two, and the Apollonian networks have degeneracy three.

The Barabási–Albert model for generating random scale-free networks is parameterized by a number m such that each vertex that is added to the graph has m previously-added vertices. It follows that any subgraph of a network formed in this way has a vertex of degree at leastm (the last vertex in the subgraph to have been added to the graph) and Barabási–Albert networks are automatically m-degenerate.

...
Wikipedia