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)
“The human species, according to the best theory I can form of it, is composed of two distinct races, the men who borrow and the men who lend.”
—Charles Lamb (1775–1834)