CHAPTER 1
Eigenvalues an d th e Laplacia n o f a grap h
1.1. Introductio n
Spectral grap h theor y ha s a lon g history . I n th e earl y days , matri x theor y
and linea r algebr a wer e use d t o analyz e adjacenc y matrice s o f graphs . Algebrai c
methods are especially effective i n treating graphs which are regulär and Symmetrie .
Sometimes, certain eigenvalues have been referred t o as the "algebrai c Connectivity "
of a graph [126]. Ther e i s a large literatur e o n algebrai c aspect s o f spectra l grap h
theory, well documented i n several surveys and books, such as Biggs [25], Cvetkovic,
Doob an d Sach s [90 , 91], and Seide l [225] .
In the pas t te n years , man y development s i n spectra l grap h theor y hav e ofte n
had a geometric flavor. Fo r example, the explicit construetion s o f expander graphs ,
due to Lubotzky-Phillips-Sarnak [194] and Margulis [196], are based on eigenvalues
and isoperimetri c propertie s o f graphs . Th e discret e analogu e o f th e Cheege r in -
equality ha s been heavil y utilize d i n the study o f random walk s and rapidl y mixin g
Markov chains [225] . Ne w spectral techniques have emerged an d the y ar e powerfu l
and well-suite d fo r dealin g wit h genera l graphs . I n a way , spectra l grap h theor y
has entere d a new era .
Just a s astronomer s stud y stella r spectr a t o determin e th e make-u p o f distan t
stars, on e o f th e mai n goal s i n grap h theor y i s t o deduc e th e .prineipal propertie s
and struetur e o f a grap h fro m it s grap h spectru m (o r fro m a shor t lis t o f easil y
computable invariants) . Th e spectra l approac h fo r genera l graph s i s a ste p i n
this direction . W e will se e that eigenvalue s ar e closel y relate d t o almos t al l majo r
invariants of a graph, linking one extremal property to another. Ther e is no question
that eigenvalue s pla y a centra l rol e i n our fundamenta l understandin g o f graphs .
The study of graph eigenvalues realizes increasingly rieh connections with man y
other area s o f mathematics . A particularly importan t developmen t i s the interac -
tion betwee n spectra l grap h theor y an d differentia l geometry . Ther e i s an interest -
ing analogy between spectral Riemannian geometry an d spectral graph theory= Th e
coneepts an d method s o f spectra l geometr y brin g usefu l tool s an d crucia l insight s
to th e stud y o f graph eigenvalues , which i n turn lea d t o ne w direction s an d result s
in spectra l geometry . Algebrai c spectra l method s ar e als o ver y useful , especiall y
for extrema l example s an d construetions . I n thi s book , w e tak e a broa d approac h
with emphasi s o n th e geometri c aspect s o f grap h eigenvalues , whil e includin g th e
algebraic aspect s a s well. Th e reade r i s not require d t o have special backgroun d i n
geometry, sinc e this boo k i s almost entirel y graph-theoretic .
i
http://dx.doi.org/10.1090/cbms/092/01
Previous Page Next Page