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.

Specific results

Let A be the adjacency matrix of a directed graph.

The characteristic polynomial of the graph is

p_A(t) = det(tI − A) ,

where I is the identity matrix. Given a particular monic polynomial, it is not known whether it is a characteristic polynomial of a graph. Two graphs are said to be isospectral if the adjacency matrices of the graphs have the same eigenvalues. Isospectral graphs need not be isomorphic, but isomorphic graphs are always isospectral.

The Ihara zeta function of the graphs given by

is another invariant of the graph. The Ihara zeta function of a connected regular graph satisfies the Riemann hypothesis if and only if the graph is a Ramanujan graph. A graph is regular if every vertex has the same number of incoming and outgoing arcs.

An important theorem states that

where n_A(k) is the number of closed walks of length k. The Ihara-Hashimoto-Bass theorem relates the zeta function to the Euler characteristic of the graph.

See also

• Symbolic dynamics
• Eigenvalue, eigenvector, and eigenspace

External links

• Spectral Graph Theory and its Applications (web page of the course of Daniel Spielman at Yale University)

• Spectral Graph Theory and its Applications, (A tutorial by Daniel Spielman, presented at FOCS 2007 Conference)

References

• Chung, Fan R. K. (1997). Spectral Graph Theory. Providence, RI: American Mathematical Society. ISSN 0160-7642; no 92.