2 1. EIGENVALUE S AN D TH E LAPLACIA N O F A GRAP H
Prom th e start , spectra l grap h theor y ha s ha d application s t o chemistr y [27] .
Eigenvalues wer e associate d wit h th e stabilit y o f molecules . Also , grap h spectr a
arise naturall y i n variou s problem s o f theoretical physic s an d quantu m mechanics ,
for example , i n minimizin g energie s o f Hamiltonia n Systems . Th e recen t progres s
on expande r graph s an d eigenvalue s wa s initiate d b y problem s i n communicatio n
networks. Th e developmen t o f rapidly mixin g Marko v chain s ha s intertwine d wit h
advances i n randomize d approximatio n algorithms . Application s o f grap h eigen -
values occu r i n numerou s area s an d i n differen t guises . However , th e underlyin g
mathematics o f spectra l grap h theor y throug h al l it s connection s t o th e pur e an d
applied, th e continuou s an d discrete , ca n b e viewe d a s a Singl e unifie d subject . I t
is this aspec t tha t w e intend t o cove r i n thi s book .
1.2. Th e Laplacia n an d eigenvalue s
Before we start to dehne eigenvalues, some explanations are in order. Th e eigen-
values we consider throughou t thi s boo k are not exactl y the sam e a s those i n Bigg s
[25] or Cvetkovic , Doo b and Sach s [90] . Basically , th e eigenvalue s ar e define d her e
in a general an d "normalized " form . Althoug h thi s migh t loo k a little complicate d
at first, ou r eigenvalue s relat e wel l to othe r grap h invariant s fo r genera l graph s i n
a wa y tha t othe r definition s (suc h a s th e eigenvalue s o f adjacenc y matrices ) ofte n
fail t o do . Th e advantage s o f thi s definitio n ar e perhap s du e t o th e fac t tha t i t i s
consistent wit h th e eigenvalue s i n spectra l geometr y an d i n stochasti c processes .
Many result s whic h wer e onl y know n fo r regulä r graph s ca n b e generalize d t o al l
graphs. Consequently , thi s provide s a coheren t treatmen t fo r a general graph . Fo r
definitions an d Standard graph-theoreti c terminology , th e reader i s referred t o [31].
In a grap h G , le t d
v
denot e th e degre e o f th e verte x v. W e firs t defin e th e
Laplacian fo r graph s withou t loop s an d multipl e edge s (th e genera l weighte d cas e
with loop s wil l b e treate d i n Sectio n 1.4). T o begin , w e conside r th e matri x L ,
defined a s follows :
dv i f u = v,
L(u,v) = { 1 i f u an d v ar e adjacent ,
0 otherwise .
Let T denot e th e diagona l matri x wit h th e (y,v)-th entr y havin g valu e d v. Th e
Laplacian o f G i s defined t o b e the matri x
C(u,v)
JL 1 1 UJ U CLliVJ . KJby y— W ,
if u an d v ar e adjacent ,
We ca n writ e
ydudv
0 otherwis e
C = T-^LT-
12'
with th e Conventio n T l (v,v) 0 fo r d
v
0. W e sa y v i s a n isolate d verte x i f
dv 0 . A graph i s said t o b e nontrivia l i f it contain s a t leas t on e edge.
Previous Page Next Page