Spectral graph theory
From Wikipedia, the free encyclopedia
In mathematics, spectral graph theory is the study of properties of a graph in relationship to the characteristic polynomial, eigenvalues, and eigenvectors of its adjacency matrix or Laplacian matrix.
An undirected graph has a symmetric adjacency matrix and therefore has real eigenvalues and a complete set of orthonormal eigenvectors.
While the adjacency matrix depends on the vertex labeling, its spectrum is a graph invariant.
Two graphs are called isospectral or cospectral if the adjacency matrices of the graphs have the same sets of eigenvalues.
Isospectral graphs need not be isomorphic, but isomorphic graphs are always isospectral. The smallest pair of nonisomorphic cospectral undirected graphs is the graph union of the 4-vertex cycle and the single-vertex graph and the 5-vertex graph, reported in 1957 by Collatz and Sinogowitz.[1][2]
Contents |
[edit] History outline
Spectral graph theory emerged in 1950s-1960s. Two major sources were research in graph theory of the relations between structural and spectral properties of graph, and research in quantum chemistry, although the connections between the two were uncovered significantly later.[3] The 1980 monograph Spectra of Graphs[4] by Cvetkovic, 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[5] The 3rd edition of Spectra of Graphs (1995) contains a summary of the further recent contributions to the subject.[3]
[edit] Facts
Almost all trees are cospectral, i.e., the share of cospectral trees on n vertices tends to 1 as n grows. [6]
[edit] References
- ^ Collatz, L. and Sinogowitz, U. "Spektren endlicher Grafen." Abh. Math. Sem. Univ. Hamburg 21, 63-77, 1957.
- ^ Eric W. Weisstein, Cospectral Graphs at MathWorld.
- ^ a b Eigenspaces of Graphs, by Dragoš Cvetković, Peter Rowlinson, Slobodan Simić (1997) ISBN 0521573521
- ^ Dragoš M. Cvetković, Michael Doob, Horst Sachs, Spectra of Graphs (1980)
- ^ Dragoš M. Cvetković, Michael Doob, Horst Sachs, A. Torgasev, Recent Results in the Theory of Graph Spectra (Annals of Disrete mathematics series, North-Holland) (1988) ISBN 0444703616
- ^ Schwenk, A. J. "Almost All Trees are Cospectral" In: New Directions in the Theory of Graphs (F. Harary, Ed.), Academic Press, New York, 1973, pp. 275-307.
