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.
Contents |
[edit] Specific results
Let A be the adjacency matrix of a directed graph.
The characteristic polynomial of the graph is
- pA(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.
The Perlis theorem states that
where nA(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.
