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
	${\ displaystyle {\ begin {pmatrix} 0 & 1 & 0 & 0 & 1 & 0 \\ 1 & 0 & 1 & 0 & 1 & 0 \\ 0 & 1 & 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 & 1 & 1 \\ 1 & 1 & 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 1 & 0 & 0 \\ }\ end {pmatrix} end {pmatrix}$	${\ displaystyle {\ begin {pmatrix} \ lambda _ {1} = 2.53948 \ ldots \\\ lambda _ {2} = 1.08247 \ ldots \\\ lambda _ {3} = 0.26114 \ ldots \\\ lambda _ {4 } = - 0.54063 \ ldots \\\ lambda _ {5} = - 1.20607 \ ldots \\\ lambda _ {6} = - 2.13639 \ ldots \\\ end {pmatrix}}}$

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 ${\ displaystyle n}$

{\ displaystyle (n-1, -1, -1, \ ldots, -1)}

.

The fully bipartite graph has the spectrum ${\ displaystyle K_ {mn}}$

{\ displaystyle ({\ sqrt {mn}}, 0, \ ldots, 0, - {\ sqrt {mn}})}

.

A graph is bipartite if and only if its spectrum is symmetric with respect to .

{\ displaystyle 0}

The largest eigenvalue a - regular graph is (Frobenius theorem), its multiplicity is the number of connected components of the graph. ${\ displaystyle k}$ ${\ displaystyle k}$

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

Web links

Brouwer-Haemers: Graph Spectrum
Spielman: Spectral Graph Theory
Pflüger, Gerrit: Advanced Seminar: Spectra of Graphs. 1. Lecture: Basics of graph theory / examples. Summer semester 2012. Uni Mainz
Chung: Diameters and Eigenvalues