Degeneracy (graph theory)
In
Degeneracy is also known as the k-core number,
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
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
Definitions and equivalences
The coloring number of a graph G was defined by
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. 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
k-Cores
A k-core of a graph G is a
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 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 et al. (2019).
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 (1983) outline an algorithm to derive the degeneracy ordering of a graph with vertex set V and edge set E in time and 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 will have at most k edges to the vertices . The l-cores of G are the subgraphs that are induced by the vertices , where i is the first vertex with degree 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
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
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
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 -vertex graph with degeneracy has at most maximal cliques whenever and ,[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
The degeneracy of random subsets of infinite lattices has been studied under the name of bootstrap percolation.
See also
Notes
- ^ Bader & Hogue (2003).
- ^ Freuder (1982).
- ^ Kirousis & Thilikos (1996).
- ^ Erdős & Hajnal (1966).
- ^ Irani (1994).
- ^ Matula & Beck (1983).
- ^ Lick & White (1970).
- ^ Barabási & Albert (1999).
- ^ Jensen & Toft (2011), 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.
- ^ Matula (1968); Lick & White (1970), Proposition 1, page 1084.
- ^ Chrobak & Eppstein (1991).
- ^ Seidman (1983).
- ^ Bollobás (1984); Łuczak (1991);Dorogovtsev, Goltsev & Mendes (2006).
- ^ Bader & Hogue (2003); Altaf-Ul-Amin et al. (2003); Wuchty & Almaas (2005).
- ^ Gaertler & Patrignani (2004); Alvarez-Hamelin et al. (2006).
- ^ Garcia-Algarra et al. (2017).
- ^ Balogh et al. (2012).
- ^ Kirkpatrick et al. (2002).
- ^ Adler (1991).
- ^ Chrobak & Eppstein (1991); Gabow & Westermann (1992); Venkateswaran (2004); Asahiro et al. (2006); Kowalik (2006).
- ^ Dean, Hutchinson & Scheinerman (1991).
- ^ Erdős & Hajnal (1966); Szekeres & Wilf (1968).
- ^ Moody & White (2003).
- ^ Robertson & Seymour (1984).
- ^ Burr & Erdős (1975).
- ^ 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
- Altaf-Ul-Amin, M.; Nishikata, K.; Koma, T.; Miyasato, T.; Shinbo, Y.; Arifuzzaman, M.; Wada, C.; Maeda, M.; Oshima, T. (2003), "Prediction of protein functions based on k-cores of protein-protein interaction networks and amino acid sequences" (PDF), Genome Informatics, 14: 498–499, archived from the original (PDF) on 2007-09-27
- Alvarez-Hamelin, José Ignacio; Dall'Asta, Luca; Barrat, Alain; Vespignani, Alessandro (2006), "k-core decomposition: a tool for the visualization of large scale networks", in Weiss, Yair; Schölkopf, Bernhard; Platt, John (eds.), Advances in Neural Information Processing Systems 18: Proceedings of the 2005 Conference, vol. 18, The MIT Press, p. 41, ISBN 0262232537
- Asahiro, Yuichi; Miyano, Eiji; Ono, Hirotaka; Zenmyo, Kouhei (2006), "Graph orientation algorithms to minimize the maximum outdegree", CATS '06: Proceedings of the 12th Computing: The Australasian Theory Symposium, Darlinghurst, Australia, Australia: Australian Computer Society, Inc., pp. 11–20, ISBN 1-920682-33-3
- Bader, Gary D.; Hogue, Christopher W. V. (2003), "An automated method for finding molecular complexes in large protein interaction networks", PMID 12525261
- Balogh, József; S2CID 2708046
- S2CID 524106, archived from the original(PDF) on 2006-11-11
- Bollobás, Béla (1984), "The evolution of sparse graphs", Graph Theory and Combinatorics, Proc. Cambridge Combinatorial Conf. in honor of Paul Erdős, Academic Press, pp. 35–57
- MR 0371701
- Chrobak, Marek;
- Dean, Alice M.; MR 1109429
- Dorogovtsev, S. N.; Goltsev, A. V.; Mendes, J. F. F. (2006), "k-core organization of complex networks", S2CID 2035
- MR 0193025
- Freuder, Eugene C. (1982), "A sufficient condition for backtrack-free search", S2CID 8624975
- S2CID 40358357
- Gaertler, Marco; Patrignani, Maurizio (2004), "Dynamic analysis of the autonomous system graph", Proc. 2nd International Workshop on Inter-Domain Performance and Simulation (IPS 2004), pp. 13–24, CiteSeerX 10.1.1.81.6841
- Garcia-Algarra, Javier; Pastor, Juan Manuel; Iriondo, Jose Maria; Galeano, Javier (2017), "Ranking of critical species to preserve the functionality of mutualistic networks using the k-core decomposition", PeerJ, 5: e3321, PMID 28533969
- Irani, Sandy (1994), "Coloring inductive graphs on-line", S2CID 181800
- Jensen, Tommy R.; Toft, Bjarne (2011), Graph Coloring Problems, Wiley Series in Discrete Mathematics and Optimization, vol. 39, John Wiley & Sons, ISBN 9781118030745
- Kirkpatrick, Scott; Wilcke, Winfried W.; Garner, Robert B.; Huels, Harald (2002), "Percolation in dense storage arrays", MR 1961703
- Kirousis, L. M.; Thilikos, D. M. (1996), "The linkage of a graph" (PDF), doi:10.1137/S0097539793255709, archived from the original(PDF) on 2011-07-21
- Kowalik, Łukasz (2006), "Approximation scheme for lowest outdegree orientation and graph density measures", Proceedings of the 17th International Symposium on Algorithms and Computation (ISAAC 2006), Lecture Notes in Computer Science, 4288, Springer-Verlag: 557–566, ISBN 978-3-540-49694-6
- Lee, Choongbum (2017), "Ramsey numbers of degenerate graphs", Annals of Mathematics, 185 (3): 791–829, S2CID 7974973
- Lick, Don R.; White, Arthur T. (1970), "k-degenerate graphs",
- Łuczak, Tomasz (1991), "Size and connectivity of the k-core of a random graph" (PDF),
- Malliaros, Fragkiskos D.; Giatsidis, Christos; Papadopoulos, Apostolos N.; Vazirgiannis, Michalis (2019), "The core decomposition of networks: theory, algorithms and applications" (PDF), The VLDB Journal, 29: 61–92, S2CID 85519668
- doi:10.1137/1010115
- S2CID 4417741
- Moody, James; JSTOR 3088904
- Seidman, Stephen B. (1983), "Network structure and minimum degree",
- Venkateswaran, V. (2004), "Minimizing maximum indegree",
- Wuchty, S.; Almaas, E. (2005), "Peeling the yeast protein network", S2CID 17659720