Spectral graph theory

A graph ${\displaystyle G}$ is said to be determined by its spectrum if any other graph with the same spectrum as ${\displaystyle G}$ is isomorphic to ${\displaystyle G}$.

Some first examples of families of graphs that are determined by their spectrum include:

• The complete graphs.
• The finite starlike trees.

A pair of graphs are said to be cospectral mates if they have the same spectrum, but are non-isomorphic.

The smallest pair of cospectral mates is {K_1,4, C₄ ∪ K₁}, comprising the 5-vertex star and the graph union of the 4-vertex cycle and the single-vertex graph, as reported by Collatz and Sinogowitz[1][2] in 1957.

The smallest pair of polyhedral cospectral mates are enneahedra with eight vertices each.[3]

Almost all trees are cospectral, i.e., as the number of vertices grows, the fraction of trees for which there exists a cospectral tree goes to 1.[4]

A pair of regular graphs are cospectral if and only if their complements are cospectral.[5]

A pair of distance-regular graphs are cospectral if and only if they have the same intersection array.

Cospectral graphs can also be constructed by means of the Sunada method.[6]

Another important source of cospectral graphs are the point-collinearity graphs and the line-intersection graphs of point-line geometries. These graphs are always cospectral but are often non-isomorphic.[7]

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, and low-dimensional topology (in particular, the study of hyperbolic 3-manifolds).

More formally, the Cheeger constant h(G) of a graph G on n vertices is defined as

${\displaystyle h(G)=\min _{0<|S|\leq {\frac {n}{2}}}{\frac {|\partial (S)|}{|S|}},}$

where the minimum is over all nonempty sets S of at most n/2 vertices and ∂(S) is the edge boundary of S, i.e., the set of edges with exactly one endpoint in S.[8]

When the graph G is d-regular, there is a relationship between h(G) and the spectral gap d − λ₂ of G. An inequality due to Dodziuk[9] and independently Alon and Milman[10] states that[11]

${\displaystyle {\frac {1}{2}}(d-\lambda _{2})\leq h(G)\leq {\sqrt {2d(d-\lambda _{2})}}.}$

This inequality is closely related to the Cheeger bound for Markov chains and can be seen as a discrete version of Cheeger's inequality in Riemannian geometry.

For general connected graphs that are not necessarily regular, an alternative inequality is given by Chung[12]^: 35

${\displaystyle {\frac {1}{2}}{\lambda }\leq {\mathbf {h} }(G)\leq {\sqrt {2\lambda }},}$

where ${\displaystyle \lambda }$ is the least nontrivial eigenvalue of the normalized Laplacian, and ${\displaystyle {\mathbf {h} }(G)}$ is the (normalized) Cheeger constant

${\displaystyle {\mathbf {h} }(G)=\min _{\emptyset \not =S\subset V(G)}{\frac {|\partial (S)|}{\min({\mathrm {vol} }(S),{\mathrm {vol} }({\bar {S}}))}}}$

where ${\displaystyle {\mathrm {vol} }(Y)}$ is the sum of degrees of vertices in ${\displaystyle Y}$.