FACTOID # 17: Though Rhode Island is the smallest state in total area, it has the longest official name: The State of Rhode Island and Providence Plantations.
 
 Home   Encyclopedia   Statistics   States A-Z   Flags   Maps   FAQ   About 
   
 
WHAT'S NEW
 

SEARCH ALL

FACTS & STATISTICS    Advanced view

Search encyclopedia, statistics and forums:

 

 

(* = Graphable)

 

 


Encyclopedia > Spectral graph theory

In mathematics, spectral graph theory is the study of properties of a graph in relationship to the eigenvalues and eigenvectors of its adjacency matrix. An undirected graph has a symmetric adjacency matrix and therefore has real eigenvalues and a complete set of orthonormal eigenvectors.


Specific results

Let M be the adjacency matrix of a graph.


The characteristic polynomial of the graph is

pM(t) = det(MtI)

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

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

where nM(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.


  Results from FactBites:
 
Spectral graph theory - Wikipedia, the free encyclopedia (277 words)
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.
Isospectral graphs need not be isomorphic, but isomorphic graphs are always isospectral, because the characteristic polynomial is a topological invariant of the graph.
The study of the topological invariants of the Cayley graph is known as geometric group theory.
  More results at FactBites »

 
 

COMMENTARY     


Share your thoughts, questions and commentary here
Your name
Your comments

Want to know more?
Search encyclopedia, statistics and forums:

 


Press Releases |  Feeds | Contact
The Wikipedia article included on this page is licensed under the GFDL.
Images may be subject to relevant owners' copyright.
All other elements are (c) copyright NationMaster.com 2003-5. All Rights Reserved.
Usage implies agreement with terms, 1022, m