Spectral graph theory

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. 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 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

: $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.

An important theorem states that

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

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.

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

Wikimedia Foundation. 2010.

Игры ⚽ Поможем написать курсовую

Look at other dictionaries:

Graph theory — In mathematics and computer science, graph theory is the study of graphs : mathematical structures used to model pairwise relations between objects from a certain collection. A graph in this context refers to a collection of vertices or nodes and … Wikipedia
Algebraic graph theory — is a branch of mathematics in which algebraic methods are applied to problems about graphs. In one sense, algebraic graph theory studies graphs in connection with linear algebra. Especially, it studies the spectrum of the adjacency matrix, the… … Wikipedia
Glossary of graph theory — Graph theory is a growing area in mathematical research, and has a large specialized vocabulary. Some authors use the same word with different meanings. Some authors use different words to mean the same thing. This page attempts to keep up with… … Wikipedia
List of graph theory topics — This is a list of graph theory topics, by Wikipedia page. See glossary of graph theory for basic terminology Contents 1 Examples and types of graphs 2 Graph coloring 3 Paths and cycles 4 … Wikipedia
Star (graph theory) — Star The star S7. (Some authors index this as S8.) Vertices k+1 Edges k … Wikipedia
Graph drawing — This article is about the general subject of graph drawing. For the annual research symposium, see International Symposium on Graph Drawing. Graphic representation of a minute fraction of the WWW, demonstrating hyperlinks. Graph drawing is an… … Wikipedia
Conductance (graph) — For other uses, see Conductance. In graph theory the conductance of a graph G=(V,E) measures how well knit the graph is: it controls how fast a random walk on G converges to a uniform distribution. The conductance of a graph is often called the… … Wikipedia
Ramanujan graph — A Ramanujan graph, named after Srinivasa Ramanujan, is a regular graph whose spectral gap is almost as large as possible (see extremal graph theory). Such graphs are excellent spectral expanders.Examples of Ramanujan graphs include the clique,… … Wikipedia
Cayley graph — In mathematics, the Cayley graph, also known as the Cayley colour graph, is the graph that encodes the structure of a discrete group. Its definition is suggested by Cayley s theorem (named after Arthur Cayley) and uses a particular, usually… … Wikipedia
Spectral sequence — In the area of mathematics known as homological algebra, especially in algebraic topology and group cohomology, a spectral sequence is a means of computing homology groups by taking successive approximations. Spectral sequences are a… … Wikipedia

Academic Dictionaries and Encyclopedias

Spectral graph theory

Look at other dictionaries:

Share the article and excerpts

Academic Dictionaries and Encyclopedias

Wikipedia

Spectral graph theory

Look at other dictionaries:

Share the article and excerpts

Direct link