Cheeger constant (graph theory)
The Cheeger constant is the minimum of all subsets of the graph G which are not empty and whose size is less than or equal to half the size of G. For this graph G, this subset A has the smallest value , and therefore 1 is the Cheeger constant of G
In mathematics, the Cheeger constant (also Cheeger number or isoperimetric number) of a graph is a numerical measure of whether or not a graph has a "bottleneck". The Cheeger constant as a measure of "bottleneckedness" is of great interest in many areas: for example, constructing well-connected networks of computers, card shuffling. The graph theoretical notion originated after the Cheeger isoperimetric constant of a compact Riemannian manifold.
The Cheeger constant is named after Jeff Cheeger.