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 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.
Read more about Spectral Graph Theory: Isospectral Graphs, Historical Outline
Famous quotes containing the words spectral, graph and/or theory:
“How does one kill fear, I wonder? How do you shoot a spectre through the heart, slash off its spectral head, take it by its spectral throat?”
—Joseph Conrad (1857–1924)
“When producers want to know what the public wants, they graph it as curves. When they want to tell the public what to get, they say it in curves.”
—Marshall McLuhan (1911–1980)
“It makes no sense to say what the objects of a theory are,
beyond saying how to interpret or reinterpret that theory in another.”
—Willard Van Orman Quine (b. 1908)