Degeneracy (graph theory)
[5] The degeneracy of a graph may be computed in linear time by an algorithm that repeatedly removes minimum-degree vertices.
[6] The connected components that are left after all vertices of degree less than k have been (repeatedly) 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 finite 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.
The Barabási–Albert model for generating random scale-free networks[8] is parameterized by a number m such that each vertex that is added to the graph has m previously-added vertices.
[9] The coloring number of a graph G was defined by Erdős & Hajnal (1966) to be the least κ for which there exists an ordering of the vertices of G in which each vertex has fewer than κ neighbors that are earlier in the ordering.
The degeneracy of a graph G was defined by Lick & White (1970) as the least k such that every induced subgraph of G contains a vertex with k or fewer neighbors.
A third, equivalent formulation is that G is k-degenerate (or has coloring number at most k + 1) if and only if the edges of G can be oriented to form a directed acyclic graph with outdegree at most k.[11] Such an orientation can be formed by orienting each edge towards the earlier of its two endpoints in a coloring number ordering.
A k-core of a graph G is a maximal connected subgraph of G in which all vertices have degree at least k. Equivalently, it is one of the connected components of the subgraph of G formed by repeatedly deleting all vertices of degree less than k. If a non-empty k-core exists, then, clearly, G has degeneracy at least k, and the degeneracy of G is the largest k for which G has a k-core.
The concept of a k-core was introduced to study the clustering structure of social networks[12] and to describe the evolution of random graphs.
[16] A survey of the topic, covering the main concepts, important algorithmic techniques as well as some application domains, may be found in Malliaros et al. (2019).
[19] Matula & Beck (1983) outline an algorithm to derive the degeneracy ordering of a graph
words of space, by storing vertices in a degree-indexed bucket queue and repeatedly removing the vertex with the smallest degree.
The degeneracy k is given by the highest degree of any vertex at the time of its removal.
at the time it is added to L. If a graph G is oriented acyclically with outdegree k, then its edges may be partitioned into k forests by choosing one forest for each outgoing edge of each node.
In the other direction, an n-vertex graph that can be partitioned into k forests has at most k(n − 1) edges and therefore has a vertex of degree at most 2k− 1 – thus, the degeneracy is less than twice the arboricity.
One may also compute in polynomial time an orientation of a graph that minimizes the outdegree but is not required to be acyclic.
[21] A k-degenerate graph has chromatic number at most k + 1; this is proved by a simple induction on the number of vertices which is exactly like the proof of the six-color theorem for planar graphs.
Since chromatic number is an upper bound on the order of the maximum clique, the latter invariant is also at most degeneracy plus one.
Since these paths must leave the two vertices of the pair via disjoint edges, a k-vertex-connected graph must have degeneracy at least k. Concepts related to k-cores but based on vertex connectivity have been studied in social network theory under the name of structural cohesion.
Although concepts of degeneracy and coloring number are frequently considered in the context of finite graphs, the original motivation for Erdős & Hajnal (1966) was the theory of infinite graphs.
For an infinite graph G, one may define the coloring number analogously to the definition for finite graphs, as the smallest cardinal number α such that there exists a well-ordering of the vertices of G in which each vertex has fewer than α neighbors that are earlier in the ordering.
The inequality between coloring and chromatic numbers holds also in this infinite setting; Erdős & Hajnal (1966) state that, at the time of publication of their paper, it was already well known.
The degeneracy of random subsets of infinite lattices has been studied under the name of bootstrap percolation.
