Spectral graph theory
Encyclopedia
In mathematics
, spectral graph theory
is the study of properties of a graph
in relationship to the characteristic polynomial
, eigenvalues, and eigenvectors of matrices associated to the graph, such as its adjacency matrix
or Laplacian matrix
.
An undirected graph has a symmetric adjacency matrix and therefore has real eigenvalues (the multiset
of which is called the graph's spectrum
) and a complete set of orthonormal eigenvectors.
While the adjacency matrix depends on the vertex labeling, its spectrum is a graph invariant.
Spectral graph theory is also concerned with graph parameters that are defined via multiplicites of eigenvalues of matrices associated to the graph, such as the Colin de Verdière number
.
or cospectral if the adjacency matrices of the graphs have equal multisets of eigenvalues.
Isospectral graphs need not be isomorphic
, but isomorphic graphs are always isospectral. The smallest pair of nonisomorphic cospectral undirected graphs is {K1,4, C4 U 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 in 1957. The smallest pair of nonisomorphic cospectral polyhedral graph
s are enneahedra
with eight vertices each.
Almost all
tree
s are cospectral, i.e., the share of cospectral trees on n vertices tends to 1 as n grows.
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. The 1980 monograph Spectra of Graphs 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. The 3rd edition of Spectra of Graphs (1995) contains a summary of the further recent contributions to the subject.
Recent research is on the following subjects, among others:
Mathematics
Mathematics is the study of quantity, space, structure, and change. Mathematicians seek out patterns and formulate new conjectures. Mathematicians resolve the truth or falsity of conjectures by mathematical proofs, which are arguments sufficient to convince other mathematicians of their validity...
, spectral graph theory
Graph theory
In mathematics and computer science, graph theory is the study of graphs, mathematical structures used to model pairwise relations between objects from a certain collection. A "graph" in this context refers to a collection of vertices or 'nodes' and a collection of edges that connect pairs of...
is the study of properties of a graph
Graph (mathematics)
In mathematics, a graph is an abstract representation of a set of objects where some pairs of the objects are connected by links. The interconnected objects are represented by mathematical abstractions called vertices, and the links that connect some pairs of vertices are called edges...
in relationship to the characteristic polynomial
Characteristic polynomial
In linear algebra, one associates a polynomial to every square matrix: its characteristic polynomial. This polynomial encodes several important properties of the matrix, most notably its eigenvalues, its determinant and its trace....
, eigenvalues, and eigenvectors of matrices associated to the graph, such as its adjacency matrix
Adjacency matrix
In mathematics and computer science, an adjacency matrix is a means of representing which vertices of a graph are adjacent to which other vertices...
or Laplacian matrix
Laplacian matrix
In the mathematical field of graph theory the Laplacian matrix, sometimes called admittance matrix or Kirchhoff matrix, is a matrix representation of a graph. Together with Kirchhoff's theorem it can be used to calculate the number of spanning trees for a given graph. The Laplacian matrix can be...
.
An undirected graph has a symmetric adjacency matrix and therefore has real eigenvalues (the multiset
Multiset
In mathematics, the notion of multiset is a generalization of the notion of set in which members are allowed to appear more than once...
of which is called the graph's spectrum
Eigendecomposition of a matrix
In the mathematical discipline of linear algebra, eigendecomposition or sometimes spectral decomposition is the factorization of a matrix into a canonical form, whereby the matrix is represented in terms of its eigenvalues and eigenvectors...
) and a complete set of orthonormal eigenvectors.
While the adjacency matrix depends on the vertex labeling, its spectrum is a graph invariant.
Spectral graph theory is also concerned with graph parameters that are defined via multiplicites of eigenvalues of matrices associated to the graph, such as the Colin de Verdière number
Colin de Verdière graph invariant
Colin de Verdière's invariant is a graph parameter \mu for any graph G introduced by Yves Colin de Verdière in 1990. It was motivated by the study of the maximum multiplicity of the second eigenvalue of certain Schrödinger operators.-Definition:...
.
Isospectral graphs
Two graphs are called isospectralIsospectral
In mathematics, two linear operators are called isospectral or cospectral if they have the same spectrum. Roughly speaking, they are supposed to have the same sets of eigenvalues, when those are counted with multiplicity....
or cospectral if the adjacency matrices of the graphs have equal multisets of eigenvalues.
Isospectral graphs need not be isomorphic
Graph isomorphism
In graph theory, an isomorphism of graphs G and H is a bijection between the vertex sets of G and H f \colon V \to V \,\!such that any two vertices u and v of G are adjacent in G if and only if ƒ and ƒ are adjacent in H...
, but isomorphic graphs are always isospectral. The smallest pair of nonisomorphic cospectral undirected graphs is {K1,4, C4 U K1}, comprising the 5-vertex star
Star (graph theory)
In graph theory, a star Sk is the complete bipartite graph K1,k: a tree with one internal node and k leaves...
and the graph union of the 4-vertex cycle
Cycle (graph theory)
In graph theory, the term cycle may refer to a closed path. If repeated vertices are allowed, it is more often called a closed walk. If the path is a simple path, with no repeated vertices or edges other than the starting and ending vertices, it may also be called a simple cycle, circuit, circle,...
and the single-vertex graph, as reported by Collatz and Sinogowitz in 1957. The smallest pair of nonisomorphic cospectral polyhedral graph
Polyhedral graph
In polyhedral combinatorics, a branch of mathematics, Steinitz's theorem is a characterization of the undirected graphs formed by the edges and vertices of three-dimensional convex polyhedra: they are exactly the 3-vertex-connected planar graphs...
s are enneahedra
Enneahedron
In geometry, a enneahedron is a polyhedron with 9 faces. There are 2606 topologically distinct enneahedra and none are regular, so this name is ambiguous.-Examples:...
with eight vertices each.
Almost all
Almost all
In mathematics, the phrase "almost all" has a number of specialised uses."Almost all" is sometimes used synonymously with "all but finitely many" or "all but a countable set" ; see almost....
tree
Tree (graph theory)
In mathematics, more specifically graph theory, a tree is an undirected graph in which any two vertices are connected by exactly one simple path. In other words, any connected graph without cycles is a tree...
s are cospectral, i.e., the share of cospectral trees on n vertices tends to 1 as n grows.
History outline
Spectral graph theory emerged in the 1950s and 1960s. Besides graph theoreticGraph theory
In mathematics and computer science, graph theory is the study of graphs, mathematical structures used to model pairwise relations between objects from a certain collection. A "graph" in this context refers to a collection of vertices or 'nodes' and a collection of edges that connect pairs of...
research on the relationship between structural and spectral properties of graphs, another major source was research in quantum chemistry
Quantum chemistry
Quantum chemistry is a branch of chemistry whose primary focus is the application of quantum mechanics in physical models and experiments of chemical systems...
, but the connections between these two lines of work were not discovered until much later. The 1980 monograph Spectra of Graphs 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. The 3rd edition of Spectra of Graphs (1995) contains a summary of the further recent contributions to the subject.
Recent research is on the following subjects, among others:
- energy of graphs (the sum of the eigenvalues)
- Colin de Verdière-type invariants
- Laplacian eigenvalues
- isoperimetric problems
- ergodicity
External links
- Spectral Graph Theory and its Applications (web page of the course of Daniel Spielman at Yale University)
- Spectral Graph Theory and its Applications, (A tutorial by Daniel Spielman, presented at FOCS 2007 Conference)
- Web page of a course on spectral graph theory at USC. Lecture notes are made available online.
- Fan Chung's revised book on Spectral Graph theory (first 4 chapters are available)
- Spectral Graph Theory page at COPPE/Federal University of Rio de Janeiro