Contents
Preface x i
Chapter 1. Eigenvalue s an d th e Laplacia n o f a graph 1
1.1. Introductio n 1
1.2. Th e Laplacia n an d eigenvalue s 2
1.3. Basi c fact s abou t th e spectru m o f a graph 6
1.4. Eigenvalue s of weighted graph s 11
1.5. Eigenvalue s an d rando m walk s 14
Chapter 2 . Isoperimetri c problem s 2 3
2.1. Histor y 2 3
2.2. Th e Cheege r constan t o f a graph 2 4
2.3. Th e edg e expansion o f a graph 2 5
2.4. Th e verte x expansio n o f a graph 2 9
2.5. A characterization o f the Cheege r constan t 3 2
2.6. Isoperimetri c inequalitie s fo r cartesia n product s 3 6
Chapter 3 . Diameter s an d eigenvalue s 4 3
3.1. Th e diarnete r o f a graph 4 3
3.2. Eigenvalue s an d distance s betwee n tw o subsets 4 5
3.3. Eigenvalue s an d distance s amon g man y subset s 4 9
3.4. Eigenvalu e uppe r bound s fo r manifold s 5 0
Chapter 4 . Paths , flows, and routin g 5 9
Previous Page Next Page