Laplacian Eigenvectors of Graphs: Perron-Frobenius and Faber-Krahn Type Theorems Book

Introduction     1
Matrix Representations of a Graph     2
Finite Differences     4
Landscapes on Graphs     4
Related Matrices     7
Graphs with a Boundary: The Discrete Dirichlet Problem     8
Generalized Graph Laplacians     10
Colin de Verdiere Matrices     11
Practical Applications of Laplacians Eigenvectors     12
Graph Laplacians     15
Basic Properties of Graph Laplacians     15
Weighted Graphs     17
The Rayleigh Quotient     18
Calculus on Graphs     19
Basic Properties of Eigenfunctions     20
Graph Automorphisms and Eigenfunctions     22
Quasi-Abelian Cayley Graphs     23
The Perron-Frobenius Theorem     26
Eigenfunctions and Nodal Domains     29
Courant's Nodal Domain Theorem     29
Proof of the Nodal Domain Theorem     33
Algebraic Connectivity, Fiedler Vectors and Perron Branches     35
Some Results for Multiple Eigenvalues     39
The Courant-Herrmann Conjecture     41
Improvements for Special Cases     42
Faria Vectors and Minimum Number of Nodal Domains     46
Sign Pattern and Nodal Domains     47
Nodal Domain Theorems for Special Graph Classes     49
Trees     49
Cographs and Threshold Graphs     54
Product Graphs and the Boolean Hypercube     58
Computational Experiments     67
Nodal Domains and Hyperplane Arrangements     67
A Hillclimbing Algorithm     69
Numerical Experiments for the Boolean Hypercube     70
Local Optima     73
Faber-Krahn Type Inequalities     77
Basic Properties of Dirichlet Operators     78
The Faber-Krahn Property     79
Unweighted Trees     81
Semiregular Trees     84
Rearrangements and Dirichlet Operators     86
Perturbations and Branches     90
Basic Notations     93
Eigenfunctions Used in Figures     97
List of Symbols     99
References     101
Index     113