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)
“Osteopath—One who argues that all human ills are caused by the pressure of hard bone upon soft tissue. The proof of his theory is to be found in the heads of those who believe it.”
—H.L. (Henry Lewis)