Degeneracy (graph theory)
Encyclopedia
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 ). 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.
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 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 most two, and the Apollonian network
s have degeneracy three.
The Barabási–Albert model for generating random
scale-free networks is parametrized 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 most m (the last vertex in the subgraph to have been added to the graph) and Barabási–Albert networks are automatically m-degenerate.
Every k-regular graph has degeneracy exactly k.
on the chromatic number, but in general these two numbers are not equal.
The degeneracy of a graph G was defined by as the least k such that every induced subgraph of G contains a vertex with k or fewer neighbors. The definition would be the same if arbitrary subgraphs are allowed in place of induced subgraphs, as a non-induced subgraph can only have vertex degrees that are smaller than or equal to the vertex degrees in the subgraph induced by the same vertex set.
The two concepts of coloring number and degeneracy are equivalent: in any finite graph the degeneracy is just one less than the coloring number. For, if a graph has an ordering with coloring number κ then in each subgraph H the vertex that belongs to H and is last in the ordering has at most κ − 1 neighbors in H. In the other direction, if G is k-degenerate, then an ordering with coloring number k + 1 can be obtained by repeatedly finding a vertex v with at most k neighbors, removing v from the graph, ordering the remaining vertices, and adding v to the end of the order.
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. Such an orientation can be formed by orienting each edge towards the earlier of its two endpoints in a coloring number ordering. In the other direction, if an orientation with outdegree k is given, an ordering with coloring number k + 1 can be obtained as a topological ordering of the resulting directed acyclic graph.
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.
A vertex
has coreness 
if it belongs to a
-core but not to any 
-core.
The concept of a k-core was introduced to study the clustering structure of social network
s and to describe the evolution of random graph
s; it has also been applied in bioinformatics
and network visualization
.
In more detail, the algorithm proceeds as follows:
At the end of the algorithm, k contains the degeneracy of G and L contains a list of vertices in an optimal ordering for the coloring number. The i-cores of G are the prefixes of L consisting of the vertices added to L after k first takes a value greater than or equal to i.
Initializing the variables L, dv, D, and k can easily be done in linear time. Finding each successively removed vertex v and adjusting the cells of D containing the neighbors of v take time proportional to the value of dv at that step; but the sum of these values is the number of edges of the graph (each edge contributes to the term in the sum for the later of its two endpoints) so the total time is linear.
by choosing one forest for each outgoing edge of each node. Thus, the arboricity
of G is at most equal to its degeneracy. 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. The edges of a graph with such an orientation may be partitioned in the same way into k pseudoforest
s, and conversely any partition of a graph's edges into k pseudoforests leads to an outdegree-k orientation (by choosing an outdegree-1 orientation for each pseudoforest), so the minimum outdegree of such an orientation is the pseudoarboricity, which again is at most equal to the degeneracy.
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. By using a greedy coloring
algorithm on an ordering with optimal coloring number, one can graph color a k-degenerate graph using at most k + 1 colors.
A k-vertex-connected graph
is a graph that cannot be partitioned into more than one component by the removal of fewer than k vertices, or equivalently a graph in which each pair of vertices can be connected by k vertex-disjoint paths. 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
.
If a graph has treewidth or pathwidth at most k, then it is a subgraph of a chordal graph
which has a perfect elimination ordering in which each vertex has at most k earlier neighbors. Therefore, the degeneracy is at most equal to the treewidth and at most equal to the pathwidth. However, there exist graphs with bounded degeneracy and unbounded treewidth, such as the grid graphs.
The as-yet-unproven Erdős–Burr conjecture
relates the degeneracy of a graph G to the Ramsey number
of G, the largest n such that any two-edge-coloring of an n-vertex complete graph
must contain a monochromatic copy of G. Specifically, the conjecture is that for any fixed value of k, the Ramsey number of k-degenerate graphs grows linearly in the number of vertices of the graphs.
α 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; state that, at the time of publication of their paper, it was already well known.
Graph theory
In mathematics and computer science, graph theory is the study of graphs, mathematical structures used to model pairwise relations between objects from a certain collection. A "graph" in this context refers to a collection of vertices or 'nodes' and a collection of edges that connect pairs of...
, a k-degenerate graph is an undirected graph in which every subgraph has a vertex of degree
Degree (graph theory)
In graph theory, the degree of a vertex of a graph is the number of edges incident to the vertex, with loops counted twice. The degree of a vertex v is denoted \deg. The maximum degree of a graph G, denoted by Δ, and the minimum degree of a graph, denoted by δ, are the maximum and minimum 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
Dense graph
In mathematics, a dense graph is a graph in which the number of edges is close to the maximal number of edges. The opposite, a graph with only a few edges, is a sparse graph...
it is, and is within a constant factor of other sparsity measures such as the arboricity
Arboricity
The arboricity of an undirected graph is the minimum number of forests into which its edges can be partitioned. Equivalently it is the minimum number of spanning forests needed to cover all the edges of the graph.-Example:...
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 ). 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
Connected component (graph theory)
In graph theory, a connected component of an undirected graph is a subgraph in which any two vertices are connected to each other by paths, and which is connected to no additional vertices. For example, the graph shown in the illustration on the right has three 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.
Examples
Every forestTree (graph theory)
In mathematics, more specifically graph theory, a tree is an undirected graph in which any two vertices are connected by exactly one simple path. In other words, any connected graph without cycles is a tree...
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 planar graph
Planar graph
In graph theory, a planar graph is a graph that can be embedded in the plane, i.e., it can be drawn on the plane in such a way that its edges intersect only at their endpoints...
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
Outerplanar graph
In graph theory, an undirected graph is an outerplanar graph if it can be drawn in the plane without crossings in such a way that all of the vertices belong to the unbounded face of the drawing. That is, no vertex is totally surrounded by edges...
has degeneracy at most two, and the Apollonian network
Apollonian network
In combinatorial mathematics, an Apollonian network is an undirected graph formed by a process of recursively subdividing a triangle into three smaller triangles. Apollonian networks may equivalently be defined as the planar 3-trees, the maximal planar chordal graphs, the uniquely 4-colorable...
s have degeneracy three.
The Barabási–Albert model for generating random
Random graph
In mathematics, a random graph is a graph that is generated by some random process. The theory of random graphs lies at the intersection between graph theory and probability theory, and studies the properties of typical random graphs.-Random graph models:...
scale-free networks is parametrized 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 most m (the last vertex in the subgraph to have been added to the graph) and Barabási–Albert networks are automatically m-degenerate.
Every k-regular graph has degeneracy exactly k.
Definitions and equivalences
The coloring number of a graph G was defined by 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. It should be distinguished from the chromatic number of G, the minimum number of colors needed to color the vertices so that no two adjacent vertices have the same color; the coloring number provides an upper boundUpper bound
In mathematics, especially in order theory, an upper bound of a subset S of some partially ordered set is an element of P which is greater than or equal to every element of S. The term lower bound is defined dually as an element of P which is lesser than or equal to every element of S...
on the chromatic number, but in general these two numbers are not equal.
The degeneracy of a graph G was defined by as the least k such that every induced subgraph of G contains a vertex with k or fewer neighbors. The definition would be the same if arbitrary subgraphs are allowed in place of induced subgraphs, as a non-induced subgraph can only have vertex degrees that are smaller than or equal to the vertex degrees in the subgraph induced by the same vertex set.
The two concepts of coloring number and degeneracy are equivalent: in any finite graph the degeneracy is just one less than the coloring number. For, if a graph has an ordering with coloring number κ then in each subgraph H the vertex that belongs to H and is last in the ordering has at most κ − 1 neighbors in H. In the other direction, if G is k-degenerate, then an ordering with coloring number k + 1 can be obtained by repeatedly finding a vertex v with at most k neighbors, removing v from the graph, ordering the remaining vertices, and adding v to the end of the order.
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
Directed acyclic graph
In mathematics and computer science, a directed acyclic graph , is a directed graph with no directed cycles. That is, it is formed by a collection of vertices and directed edges, each edge connecting one vertex to another, such that there is no way to start at some vertex v and follow a sequence of...
with outdegree
Degree (graph theory)
In graph theory, the degree of a vertex of a graph is the number of edges incident to the vertex, with loops counted twice. The degree of a vertex v is denoted \deg. The maximum degree of a graph G, denoted by Δ, and the minimum degree of a graph, denoted by δ, are the maximum and minimum degree...
at most k. Such an orientation can be formed by orienting each edge towards the earlier of its two endpoints in a coloring number ordering. In the other direction, if an orientation with outdegree k is given, an ordering with coloring number k + 1 can be obtained as a topological ordering of the resulting directed acyclic graph.
k-Cores
A k-core of a graph G is a maximalMaximal element
In mathematics, especially in order theory, a maximal element of a subset S of some partially ordered set is an element of S that is not smaller than any other element in S. The term minimal element is defined dually...
connected subgraph of G in which all vertices have degree at least k. Equivalently, it is one of the connected components
Connected component (graph theory)
In graph theory, a connected component of an undirected graph is a subgraph in which any two vertices are connected to each other by paths, and which is connected to no additional vertices. For example, the graph shown in the illustration on the right has three 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.
A vertex
has coreness if it belongs to a-core but not to any -core.The concept of a k-core was introduced to study the clustering structure of social network
Social network
A social network is a social structure made up of individuals called "nodes", which are tied by one or more specific types of interdependency, such as friendship, kinship, common interest, financial exchange, dislike, sexual relationships, or relationships of beliefs, knowledge or prestige.Social...
s and to describe the evolution of random graph
Random graph
In mathematics, a random graph is a graph that is generated by some random process. The theory of random graphs lies at the intersection between graph theory and probability theory, and studies the properties of typical random graphs.-Random graph models:...
s; it has also been applied in bioinformatics
Bioinformatics
Bioinformatics is the application of computer science and information technology to the field of biology and medicine. Bioinformatics deals with algorithms, databases and information systems, web technologies, artificial intelligence and soft computing, information and computation theory, software...
and network visualization
Graph drawing
Graph drawing is an area of mathematics and computer science combining methods from geometric graph theory and information visualization to derive two-dimensional depictions of graphs arising from applications such as social network analysis, cartography, and bioinformatics...
.
Algorithms
As describe, it is possible to find a vertex ordering of a finite graph G that optimizes the coloring number of the ordering, in linear time, by repeatedly removing the vertex of smallest degree.In more detail, the algorithm proceeds as follows:
- Initialize an output list L.
- Compute a number dv for each vertex v in G, the number of neighbors of v that are not already in L. Initially, these numbers are just the degrees of the vertices.
- Initialize an array D such that D[i] contains a list of the vertices v that are not already in L for which dv = i.
- Initialize k to 0.
- Repeat n times:
- Scan the array cells D[0], D[1], ... until finding an i for which D[i] is nonempty.
- Set k to max(k,i)
- Select a vertex v from D[i]. Add v to the beginning of L and remove it from D[i].
- For each neighbor w of v, subtract one from dw and move w to the cell of D corresponding to the new value of dw.
At the end of the algorithm, k contains the degeneracy of G and L contains a list of vertices in an optimal ordering for the coloring number. The i-cores of G are the prefixes of L consisting of the vertices added to L after k first takes a value greater than or equal to i.
Initializing the variables L, dv, D, and k can easily be done in linear time. Finding each successively removed vertex v and adjusting the cells of D containing the neighbors of v take time proportional to the value of dv at that step; but the sum of these values is the number of edges of the graph (each edge contributes to the term in the sum for the later of its two endpoints) so the total time is linear.
Relation to other graph parameters
If a graph G is oriented acyclically with outdegree k, then its edges may be partitioned into k forestsTree (graph theory)
In mathematics, more specifically graph theory, a tree is an undirected graph in which any two vertices are connected by exactly one simple path. In other words, any connected graph without cycles is a tree...
by choosing one forest for each outgoing edge of each node. Thus, the arboricity
Arboricity
The arboricity of an undirected graph is the minimum number of forests into which its edges can be partitioned. Equivalently it is the minimum number of spanning forests needed to cover all the edges of the graph.-Example:...
of G is at most equal to its degeneracy. 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. The edges of a graph with such an orientation may be partitioned in the same way into k pseudoforest
Pseudoforest
In graph theory, a pseudoforest is an undirected graph in which every connected component has at most one cycle. That is, it is a system of vertices and edges connecting pairs of vertices, such that no two cycles of consecutive edges share any vertex with each other, nor can any two cycles be...
s, and conversely any partition of a graph's edges into k pseudoforests leads to an outdegree-k orientation (by choosing an outdegree-1 orientation for each pseudoforest), so the minimum outdegree of such an orientation is the pseudoarboricity, which again is at most equal to the degeneracy.
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. By using a greedy coloring
Greedy coloring
In the study of graph coloring problems in mathematics and computer science, a greedy coloring is a coloring of the vertices of a graph formed by a greedy algorithm that considers the vertices of the graph in sequence and assigns each vertex its first available color...
algorithm on an ordering with optimal coloring number, one can graph color a k-degenerate graph using at most k + 1 colors.
A k-vertex-connected graph
K-vertex-connected graph
In graph theory, a graph G with vertex set V is said to be k-vertex-connected if the graph remains connected when you delete fewer than k vertices from the graph...
is a graph that cannot be partitioned into more than one component by the removal of fewer than k vertices, or equivalently a graph in which each pair of vertices can be connected by k vertex-disjoint paths. 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
Structural cohesion
Structural cohesion is the sociological conception of cohesion in social groups. It is defined as the minimal number of actors in a social network that need to be removed to disconnect at least two actors in the remaining group. It is thus identical to the question of the node connectivity of a...
.
If a graph has treewidth or pathwidth at most k, then it is a subgraph of a chordal graph
Chordal graph
In the mathematical area of graph theory, a graph is chordal if each of its cycles of four or more nodes has a chord, which is an edge joining two nodes that are not adjacent in the cycle. An equivalent definition is that any chordless cycles have at most three nodes...
which has a perfect elimination ordering in which each vertex has at most k earlier neighbors. Therefore, the degeneracy is at most equal to the treewidth and at most equal to the pathwidth. However, there exist graphs with bounded degeneracy and unbounded treewidth, such as the grid graphs.
The as-yet-unproven Erdős–Burr conjecture
Erdos–Burr conjecture
In mathematics, the Erdős–Burr conjecture is an unsolved problem concerning the Ramsey number of sparse graphs. The conjecture is named after Paul Erdős and Stefan Burr, and is one of many conjectures named after Erdős; it states that the Ramsey number of graphs in any sparse family of graphs...
relates the degeneracy of a graph G to the Ramsey number
Ramsey theory
Ramsey theory, named after the British mathematician and philosopher Frank P. Ramsey, is a branch of mathematics that studies the conditions under which order must appear...
of G, the largest n such that any two-edge-coloring of an n-vertex complete graph
Complete graph
In the mathematical field of graph theory, a complete graph is a simple undirected graph in which every pair of distinct vertices is connected by a unique edge.-Properties:...
must contain a monochromatic copy of G. Specifically, the conjecture is that for any fixed value of k, the Ramsey number of k-degenerate graphs grows linearly in the number of vertices of the graphs.
Infinite graphs
Although concepts of degeneracy and coloring number are frequently considered in the context of finite graphs, the original motivation for 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 numberCardinal number
In mathematics, cardinal numbers, or cardinals for short, are a generalization of the natural numbers used to measure the cardinality of sets. The cardinality of a finite set is a natural number – the number of elements in the set. The transfinite cardinal numbers describe the sizes of infinite...
α 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; state that, at the time of publication of their paper, it was already well known.