Degeneracy (graph theory)

<p>In <a href="/facts/Graph_theory/VVPCd4TX">graph theory</a>, a k-degenerate graph is an <a href="/facts/Undirected_graph/kw3eIBUe">undirected graph</a> in which every subgraph has at least one vertex of <a href="/facts/Degree_(graph_theory)/LnFFpI8v">degree</a> at most 
  
    
      
        k
      
    
    {\displaystyle k}
  
. That is, some vertex in the subgraph touches 
  
    
      
        k
      
    
    {\displaystyle k}
  
 or fewer of the subgraph's edges. The degeneracy of a graph is the smallest value of 
  
    
      
        k
      
    
    {\displaystyle k}
  
 for which it is 
  
    
      
        k
      
    
    {\displaystyle k}
  
-degenerate. The degeneracy of a graph is a measure of how <a href="/facts/Dense_graph/xFC7b7s9">sparse</a> it is, and is within a constant factor of other sparsity measures such as the <a href="/facts/Arboricity/JjfuCv8r">arboricity</a> of a graph.
</p><p>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 <a href="/facts/George_Szekeres/SYAhPzEF">Szekeres</a> and <a href="/facts/Herbert_Wilf/SpfnF0dc"> Wilf</a> (1968)). The 
  
    
      
        k
      
    
    {\displaystyle k}
  
-degenerate graphs have also been called k-inductive graphs. The degeneracy of a graph may be computed in <a href="/facts/Linear_time/77T62gmf">linear time</a> by an algorithm that repeatedly removes minimum-degree vertices. The <a href="/facts/Connected_component_(graph_theory)/5owVSXtY">connected components</a> that are left after all vertices of degree less than 
  
    
      
        k
      
    
    {\displaystyle k}
  
 have been (repeatedly) removed are called the k-cores of the graph and the degeneracy of a graph is the largest value 
  
    
      
        k
      
    
    {\displaystyle k}
  
 such that it has a 
  
    
      
        k
      
    
    {\displaystyle k}
  
-core.
</p>

Degeneracy (graph theory) open-in-new

Degeneracy (graph theory)