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

\zeta_A(t) = \frac{1}{\det (I-tA)},

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

t \frac{d}{dt} \log \zeta_A(t) = \sum_{k=1}^\infty n_A(k) t^k

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.

[edit] See also

[edit] External links

[edit] References

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