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)
“In this Journal, my pen is a delicate needle point, tracing out a graph of temperament so as to show its daily fluctuations: grave and gay, up and down, lamentation and revelry, self-love and self-disgust. You get here all my thoughts and opinions, always irresponsible and often contradictory or mutually exclusive, all my moods and vapours, all the varying reactions to environment of this jelly which is I.”
—W.N.P. Barbellion (1889–1919)
“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)