def
SimpleGraph.annihilationNumber
{α : Type u_1}
[Fintype α]
(G : SimpleGraph α)
[DecidableRel G.Adj]
:
The annihilation number of a graph. This is the largest number of degrees that can be added together without going over the total number of edges of that graph.
Equations
- G.annihilationNumber = {S ∈ Finset.Iic G.degreeMultiset | S.sum ≤ G.edgeFinset.card}.sup Multiset.card
Instances For
noncomputable def
SimpleGraph.annihilationNumber'
{α : Type u_1}
[Fintype α]
(G : SimpleGraph α)
[DecidableRel G.Adj]
:
Computes the annihilation number of a graph G.
It calculates the degree sequence, sorts it ascendingly, and finds the largest prefix length 'k'
(where 0 ≤ k ≤ |V(G)|) such that the sum of the prefix is less than or equal to the sum of the corresponding suffix.
Equations
- One or more equations did not get rendered due to their size.