- Spectral graph theory
In
mathematics , spectralgraph theory is the study of properties of a graph in relationship to thecharacteristic polynomial ,eigenvalue s, andeigenvector s of itsadjacency matrix orLaplacian matrix . Anundirected graph has a symmetric adjacency matrix and therefore has real eigenvalues and a complete set oforthonormal 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 adirected graph . Two graphs are said to beisospectral if the adjacency matrices of the graphs have the same eigenvalues. Isospectral graphs need not beisomorphic , but isomorphic graphs are always isospectral.The
characteristic polynomial of the graph is :"p""A"("t") = det("tI" − "A") ,where "I" is the identity matrix.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 theRiemann hypothesis if and only if the graph is aRamanujan 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 theEuler characteristic of the graph.ee also
*
Symbolic dynamics
*Eigenvalue, eigenvector, and eigenspace External links
* [http://www.cs.yale.edu/homes/spielman/eigs/ Spectral Graph Theory and its Applications (web page of the course of Daniel Spielman at Yale University)]
* [http://cs-www.cs.yale.edu/homes/spielman/sgta/ Spectral Graph Theory and its Applications, (A tutorial by Daniel Spielman, presented at FOCS 2007 Conference) ]
References
*cite book | author=Chung, Fan R. K. | title=Spectral Graph Theory | location=Providence, RI | publisher=American Mathematical Society | year=1997 | id=ISSN|0160-7642; no 92
Wikimedia Foundation. 2010.