Laplacian eigenvectors of graphs. Perron-Frobenius and Faber-Krahn type theorems (Q2642409)

The eigenvalues of graphs, most often defined as the eigenvalues of the adjacency matrix, have received much attention in 50's and 60's of the 20th century as a means of characterizing classes of graphs and for obtaining bounds on properties such as diameter, girth, chromatic number, connectivity, etc. The interest has since then shifted somewhat from the adjacency spectrum to the spectrum of the closely related graph Laplacian. In particular, Laplacian graph spectra are being investigated as a means of characterizing large ``small world networks'' and random graphs. This book focuses on mostly geometric properties of the eigenvectors themselves. Chapter 1 provides necessarry definitions (matrix representations, landscapes, generalized graph Laplacians). In Chapter 2 results concerning Laplacians are summarized (Rayleigh quotient, basic properties of eigenfunctions, quasi-abelian Cayley graphs, Perron-Frobenius theorem). Chapters 3 and 4 deal with eigenfunctions and nodal domains (Courant's nodal domain theorem, algebraic connectivity, Fiedler vectors, Perron branches, Courant-Herrmann conjecture). In Chapter 5 various computational experiments are described (nodal domains and hyperplane arrangements, hillclimbing algorithm, etc.). Finally, Chapter 6 covers Faber-Krahn type inequalities (unweighted and semiregular trees, rearrangements and Dirichlet operators, perturbations).