1. Introduction ................................................. 1
1.1. Matrix Representations of a Graph ....................... 2
1.2. Finite Differences ...................................... 4
1.3. Landscapes on Graphs .................................... 4
1.4. Related Matrices ........................................ 7
1.5. Graphs with a Boundary: The Discrete Dirichlet
Problem ................................................. 8
1.6. Generalized Graph Laplacians ........................... 10
1.7. Colin de Verdiere Matrices ............................. 11
1.8. Practical Applications of Laplacians Eigenvectors ...... 12
2. Graph Laplacians ............................................ 15
2.1. Basic Properties of Graph Laplacians ................... 15
2.2. Weighted Graphs ........................................ 17
2.3. The Rayleigh Quotient .................................. 18
2.4. Calculus on Graphs ..................................... 19
2.5. Basic Properties of Eigenfunctions ..................... 20
2.6. Graph Automorphisms and Eigenfunctions ................. 22
2.7. Quasi-Abelian Cayley Graphs ............................ 23
2.8. The Perron-Frobenius Theorem ........................... 26
3. Eigenfunctions and Nodal Domains ............................ 29
3.1. Courant's Nodal Domain Theorem ......................... 29
3.2. Proof of the Nodal Domain Theorem ...................... 33
3.3. Algebraic Connectivity, Fiedler Vectors and Perron
Branches ............................................... 35
3.4. Some Results for Multiple Eigenvalues .................. 39
3.5. The Courant-Herrmann Conjecture ........................ 41
3.6. Improvements for Special Cases ......................... 42
3.7. Faria Vectors and Minimum Number of Nodal Domains ...... 46
3.8. Sign Pattern and Nodal Domains ......................... 47
4. Nodal Domain Theorems for Special Graph Classes ............. 49
4.1. Trees .................................................. 49
4.2. Cographs and Threshold Graphs .......................... 54
4.3. Product Graphs and the Boolean Hypercube 58
5. Computational Experiments ................................... 67
5.1. Nodal Domains and Hyperplane Arrangements .............. 67
5.2. A Hillclimbing Algorithm ............................... 69
5.3. Numerical Experiments for the Boolean Hypercube ........ 70
5.4. Local Optima ........................................... 73
6. Faber-Krahn Type Inequalities ............................... 77
6.1. Basic Properties of Dirichlet Operators ................ 78
6.2. The Faber-Krahn Property ............................... 79
6.3. Unweighted Trees ....................................... 81
6.4. Semiregular Trees ...................................... 84
6.5. Rearrangements and Dirichlet Operators ................. 86
6.6. Perturbations and Branches ............................. 90
A. Basic Notations ............................................. 93
В. Eigenfunctions Used in Figures .............................. 97
С. List of Symbols ............................................. 99
References .................................................... 101
Index ......................................................... 113
|
