Degeneracy (graph theory)

From HandWiki
Short description: Measurement of graph sparsity
"K-core" redirects here. The core of a graph is a different concept.
A 2-degenerate graph: each vertex has at most two neighbors to its left, so the rightmost vertex of any subgraph has degree at most two. Its 2-core, the subgraph remaining after repeatedly deleting vertices of degree less than two, is shaded.

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,[1] width,[2] and linkage,[3] and is essentially the same as the coloring number[4] or Szekeres–Wilf number (named after Szekeres and Wilf (1968)). k-degenerate graphs have also been called k-inductive graphs.[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.

Examples

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. Every 1-degenerate graph is a forest.

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 most two,[7] and the Apollonian networks have degeneracy three.

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. 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. More strongly, the degeneracy of a graph equals its maximum vertex degree if and only if at least one of the connected components of the graph is regular of maximum degree. For all other graphs, the degeneracy is strictly less than the maximum degree.[9]

Definitions and equivalences

The coloring number of a graph G was defined by (Erdős Hajnal) 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 ordering which determines the coloring number provides an order to color the vertices of G with the coloring number, but in general the chromatic number may be smaller.

The degeneracy of a graph G was defined by (Lick White) 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.[10] 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.[11] 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 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.

A vertex [math]\displaystyle{ u }[/math] has coreness [math]\displaystyle{ c }[/math] if it belongs to a [math]\displaystyle{ c }[/math]-core but not to any [math]\displaystyle{ (c+1) }[/math]-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.[13] It has also been applied in bioinformatics,[14] network visualization,[15] and resilience of networks in ecology.[16] A survey of the topic, covering the main concepts, important algorithmic techniques as well as some application domains, may be found in (Malliaros Giatsidis).

Bootstrap percolation is a random process studied as an epidemic model[17] and as a model for fault tolerance for distributed computing.[18] It consists of selecting a random subset of active cells from a lattice or other space, and then considering the k-core of the induced subgraph of this subset.[19]

Algorithms

(Matula Beck) outline an algorithm to derive the degeneracy ordering of a graph [math]\displaystyle{ G = (V, E) }[/math] with vertex set V and edge set E in [math]\displaystyle{ \mathcal{O}(\vert V \vert + \vert E \vert) }[/math] time and [math]\displaystyle{ \mathcal{O}(\vert V \vert) }[/math] 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.

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 not already in L, 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, any vertex [math]\displaystyle{ L[i] }[/math] will have at most k edges to the vertices [math]\displaystyle{ L[1,\ldots,i-1] }[/math]. The l-cores of G are the subgraphs [math]\displaystyle{ H_l \subset G }[/math] that are induced by the vertices [math]\displaystyle{ L[1,\ldots,i] }[/math], where i is the first vertex with degree [math]\displaystyle{ \geq l }[/math] at the time it is added to L.

Relation to other graph parameters

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. 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 pseudoforests, 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.[20] The thickness is also within a constant factor of the arboricity, and therefore also of the degeneracy.[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. 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.[22]

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.[23]

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.[24]

The Burr–Erdős conjecture relates the degeneracy of a graph G to the Ramsey number of G, the least 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.[25] The conjecture was proven by (Lee 2017).

Any [math]\displaystyle{ n }[/math]-vertex graph with degeneracy [math]\displaystyle{ d }[/math] has at most [math]\displaystyle{ (n-d)3^{d/3} }[/math] maximal cliques whenever [math]\displaystyle{ d \equiv 0 \mod 3 }[/math] and [math]\displaystyle{ n \geq d+3 }[/math],[26] so the class of graphs with bounded degeneracy is said to have few cliques.

Infinite graphs

Although concepts of degeneracy and coloring number are frequently considered in the context of finite graphs, the original motivation for (Erdős Hajnal) 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) 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.

See also

Notes

  1. ↑ Bader & Hogue (2003).
  2. ↑ Freuder (1982).
  3. ↑ Kirousis & Thilikos (1996).
  4. ↑ Erdős & Hajnal (1966).
  5. ↑ Irani (1994).
  6. ↑ Matula & Beck (1983).
  7. ↑ (Lick White).
  8. ↑ (Barabási Albert).
  9. ↑ (Jensen Toft), p. 78: "It is easy to see that col(G) = Δ(G) + 1 if and only if G has a Δ(G)-regular component." In the notation used by Jensen and Toft, col(G) is the degeneracy plus one, and Δ(G) is the maximum vertex degree.
  10. ↑ (Matula 1968); (Lick White), Proposition 1, page 1084.
  11. ↑ (Chrobak Eppstein).
  12. ↑ (Seidman 1983).
  13. ↑ (Bollobás 1984); (Łuczak 1991);(Dorogovtsev Goltsev).
  14. ↑ (Bader Hogue); (Altaf-Ul-Amin Nishikata); (Wuchty Almaas).
  15. ↑ (Gaertler Patrignani); (Alvarez-Hamelin Dall'Asta).
  16. ↑ Garcia-Algarra et al. (2017).
  17. ↑ Balogh et al. (2012).
  18. ↑ Kirkpatrick et al. (2002).
  19. ↑ Adler (1991).
  20. ↑ (Chrobak Eppstein); (Gabow Westermann); (Venkateswaran 2004); (Asahiro Miyano); (Kowalik 2006).
  21. ↑ Dean, Hutchinson & Scheinerman (1991).
  22. ↑ (Erdős Hajnal); (Szekeres Wilf).
  23. ↑ (Moody White).
  24. ↑ (Robertson Seymour).
  25. ↑ (Burr Erdős).
  26. ↑ Eppstein, D., Löffler, M., & Strash, D. (2010). Listing All Maximal Cliques in Sparse Graphs in Near-Optimal Time. In O. Cheong, K.-Y. Chwa, & K. Park (Eds.), Algorithms and Computation (Vol. 6506, pp. 403–414). Berlin, Heidelberg: Springer Berlin Heidelberg. https://doi.org/10.1007/978-3-642-17517-6_36

References



Retrieved from "https://handwiki.org/wiki/index.php?title=Degeneracy_(graph_theory)&oldid=3360860"