spectral graph theory

In mathematics, spectral graph theory is the study of properties of a graph in relationship to the characteristic polynomials, eigenvalues and eigenvectors of its adjacency matrix or Laplace 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 M be the adjacency matrix of a graph. The characteristic polynomial of the graph is

p_M(t) = det(M − tI)

Given a particular polynomial, it is not known if a corresponding adjacency matrix can be deduced. 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, because the characteristic polynomial is a topological invariant of the graph. The Ihara zeta function of the graph is given by

\zeta_M(t) = \frac{1}{\det (I-tM)}

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

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

where n_M(k) is the number of closed paths (with no backtracking or repetition) of length k. The Ihara-Hashimoto-Bass theorem relates the zeta function to the Euler characteristic of the graph. The study of the topological invariants of the Cayley graph is known as geometric group theory.

<< Previous

Word Browser

Next >>

lalah sune
ochsenhausen
jack hayward
minicoy island
no need to argue
unagisaki hocho
2004 fh
japanese counter word
aiguille delaz
crepuscular rays
bulkington

hyperreal
dhivehi language
caroline dhavernas
kanowna, western australia
north eurasia
ronia the robber's daughter
anglo america
the conqueror worm
to the faithful departed
kozielsk
starobielsk

muhammad thakurufaanu al azam
todd county
elizabeth george
yellow pine
tipton county
apache point observatory
wiyn observatory
wall gun
national optical astronomy observatory
thurston county
powergen

addu
wan
huvadhu
gan
thomas county
fua mulaku
dolores o'riordan
list of multivariable calculus topics
texas county
canto general
teton county