Spectrum (graph theory)
In graph theory, the spectrum is used to investigate the properties of graphs. The corresponding area is called Algebraic Graph Theory or Spectral Graph Theory . The calculation of the spectrum of a graph enables a very effective algorithm for graph drawing ( Hall's algorithm .) Expander graphs can also be characterized using spectral methods.
definition
The spectrum of a graph is the sequence (ordered by size) of the eigenvalues of its adjacency matrix . The latter are also referred to as the eigenvalues of the graph.
( Undirected graphs have a symmetric adjacency matrix and therefore real eigenvalues.)
graph | Adjacency matrix | Eigenvalues |
---|---|---|
|
|
The eigenvalues of the Laplace matrix of the graph are often referred to as its spectrum.
Examples
The following examples relate to the spectrum of the adjacency matrix.
- The full graph on nodes has the spectrum
- .
- The fully bipartite graph has the spectrum
- .
- A graph is bipartite if and only if its spectrum is symmetric with respect to .
- The largest eigenvalue a - regular graph is (Frobenius theorem), its multiplicity is the number of connected components of the graph.
literature
- Cvetković, Dragoš M .; Doob, Michael; Sachs, Horst: Spectra of graphs. Theory and applications. Third edition. Johann Ambrosius Barth, Heidelberg, 1995. ISBN 3-335-00407-8
- Biggs, Norman: Algebraic graph theory. Second edition. Cambridge Mathematical Library. Cambridge University Press, Cambridge, 1993. ISBN 0-521-45897-8
- Godsil, Chris; Royle, Gordon: Algebraic graph theory. Graduate Texts in Mathematics, 207. Springer-Verlag, New York, 2001. ISBN 0-387-95241-1 ; 0-387-95220-9