While the adjacency matrix depends on the vertex labeling, its
spectrum is a
graph invariant, although not a complete one.
Spectral graph theory is also concerned with graph parameters that are defined via multiplicities of eigenvalues of matrices associated to the graph, such as the
Colin de Verdière number.
Cospectral graphs
Two graphs are called cospectral or isospectral if the adjacency matrices of the graphs are
isospectral, that is, if the adjacency matrices have equal
multisets of eigenvalues.
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 {K1,4, C4 ∪ K1}, 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]
Finding cospectral graphs
Almost alltrees 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]
Cheeger inequality
The famous
Cheeger's inequality from
Riemannian geometry has a discrete analogue involving the Laplacian matrix; this is perhaps the most important theorem in spectral graph theory and one of the most useful facts in algorithmic applications. It approximates the sparsest cut of a graph through the second eigenvalue of its Laplacian.
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
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]
Cheeger inequality
When the graph G is d-regular, there is a relationship between h(G) and the spectral gap d − λ2 of G. An inequality due to Dodziuk[9] and independently
Alon and
Milman[10] states that[11]
This bound has been applied to establish e.g. algebraic proofs of the
Erdős–Ko–Rado theorem and its analogue for intersecting families of subspaces over
finite fields.[14]
For general graphs which are not necessarily regular, a similar upper bound for the independence number can be derived by using the maximum eigenvalue
of the normalized Laplacian[12] of :
where and denote the maximum and minimum degree in , respectively. This a consequence of a more general inequality (pp. 109 in
[12]):
where is an independent set of vertices and denotes the sum of degrees of vertices in .
Historical outline
Spectral graph theory emerged in the 1950s and 1960s. Besides
graph theoretic research on the relationship between structural and spectral properties of graphs, another major source was research in
quantum chemistry, but the connections between these two lines of work were not discovered until much later.[15] The 1980 monograph Spectra of Graphs[16] by Cvetković, Doob, and Sachs summarised nearly all research to date in the area. In 1988 it was updated by the survey Recent Results in the Theory of Graph Spectra.[17] The 3rd edition of Spectra of Graphs (1995) contains a summary of the further recent contributions to the subject.[15] Discrete geometric analysis created and developed by
Toshikazu Sunada in the 2000s deals with spectral graph theory in terms of discrete Laplacians associated with weighted graphs,[18] and finds application in various fields, including
shape analysis. In most recent years, the spectral graph theory has expanded to vertex-varying graphs often encountered in many real-life applications.[19][20][21][22]
^Hosoya, Haruo; Nagashima, Umpei; Hyugaji, Sachiko (1994), "Topological twin graphs. Smallest pair of isospectral polyhedral graphs with eight vertices", Journal of Chemical Information and Modeling, 34 (2): 428–431,
doi:
10.1021/ci00018a033.
^Sakiyama, Akie; Watanabe, Kana; Tanaka, Yuichi (September 2016). "Spectral Graph Wavelets and Filter Banks With Low Approximation Error". IEEE Transactions on Signal and Information Processing over Networks. 2 (3): 230–245.
doi:
10.1109/tsipn.2016.2581303.
ISSN2373-776X.
S2CID2052898.