Laplacian Eigenvectors of Graphs

Perron-Frobenius and Faber-Krahn Type Theorems

verfasst von: Türker Biyikoğu, Josef Leydold, Peter F. Stadler

Verlag: Springer Berlin Heidelberg

Buchreihe : Lecture Notes in Mathematics

Enthalten in: Springer Professional "Wirtschaft+Technik" , Springer Professional "Technik" , Springer Professional "Wirtschaft"

Einloggen, um Zugang zu erhalten

Über dieses Buch

Eigenvectors of graph Laplacians have not, to date, been the subject of expository articles and thus they may seem a surprising topic for a book. The authors propose two motivations for this new LNM volume: (1) There are fascinating subtle differences between the properties of solutions of Schrödinger equations on manifolds on the one hand, and their discrete analogs on graphs. (2) “Geometric” properties of (cost) functions defined on the vertex sets of graphs are of practical interest for heuristic optimization algorithms. The observation that the cost functions of quite a few of the well-studied combinatorial optimization problems are eigenvectors of associated graph Laplacians has prompted the investigation of such eigenvectors.

The volume investigates the structure of eigenvectors and looks at the number of their sign graphs (“nodal domains”), Perron components, graphs with extremal properties with respect to eigenvectors. The Rayleigh quotient and rearrangement of graphs form the main methodology.

Inhaltsverzeichnis

Frontmatter

1. Introduction

The foundations of spectral graph theory were laid in the fifties and sixties of the 20th century. The eigenvalues of graphs, most often defined as the eigenvalues of the adjacency matrix, have since then received much attention as a means of characterizing classes of graphs and for obtaining bounds on properties such as the diameter, girth, chromatic number, connectivity [14, 17, 45, 46, 83, 85]. The interest has since then shifted somewhat from the adjacency spectrum to the spectrum of the closely related graph Laplacian [14, 35, 41, 85, 88, 137, 139]. In particular, Laplacian graph spectra are being investigated as a means of characterizing large “small world networks” and random graphs, see e.g. [33, 34, 119] for a few examples. For the most part, the theory is still concerned with the eigenvalues.

2. Graph Laplacians

In this chapter we recall the definition of (generalized) graph Laplacians and present the basic properties of their eigenfunctions. Moreover, we establish the main tools that will be used throughout the book. For a thorough overview of other properties of graph Laplacians not required for our investigations of eigenfunctions we refer the interested reader to the survey by Merris [133].

3. Eigenfunctions and Nodal Domains

In the previous chapter we have seen that (due to the Perron-Frobenius Theorem) the eigenfunctions of the first eigenvalue λ1 have all entries positive (or negative) for a generalized Laplacian matrix M of a connected graph G. Fiedler [67] has shown that for eigenfunctions of the smallest nonzero eigenvalue of a graph the subgraph induced by nonpositive vertices (i.e., vertices with nonpositive function values) and the subgraph induced by nonnegative vertices are both connected. In other words, an eigenfunction of the second eigenvalue has exactly two weak nodal domains (also called weak sign graphs).

4. Nodal Domain Theorems for Special Graph Classes

In Sect. 3.6 we have seen that the upper bound for the number of (strong or weak) nodal domains that is given by the discrete nodal domain theorem cannot be improved without further restrictions. On the other hand, we have seen that there exist graphs where this bound is not sharp. In general it is unknown, whether this upper bound is sharp for an arbitrary graph. The situation is similar for the (trivial) lower bound in Thm. 3.33. Furthermore, no generalmethod is known to construct an eigenfunction of a given eigenvalue λk that maximizes or minimizes the number of (strong or weak) nodal domains. In this chapter we take a closer look to the situation for trees, cographs, and product graphs (in particular to the Boolean hypercube), where it is possible to derive improved upper and lower bounds.

5. Computational Experiments

It is relatively easy to compute the number of nodal domains for a given eigenfunction1. Thus it is no problem to compute the possible number of nodal domains when all eigenvalues are simple. The situation changes completely in the case of degenerate eigenvalues because then the number of nodal domains may vary considerably depending on which eigenfunction from the r-dimensional eigenspace of λk is chosen. Hence, given a fixed graph G(V,E) and an eigenvalue λk of multiplicity r three questions immediately arise.

6. Faber-Krahn Type Inequalities

The celebrated Faber-Krahn Theorem gives an important isoperimetric inequality concerning Dirichlet eigenvalues. It states that the ball has lowest first Dirichlet eigenvalue amongst all bounded domains of the same volume in R (with the standard Euclidean metric). It has been first conjectured by Rayleigh and proved independently by Faber [61] and Krahn [118] for the R; a proof of the generalized version can be found for example in [29]. The Faber-Krahn theorem can also be rephrased in the following way: for all drums with the same area and same tension the circular-shaped has the lowest tone.

Backmatter

Titel: Laplacian Eigenvectors of Graphs
verfasst von: Türker Biyikoğu
Josef Leydold
Peter F. Stadler
Verlag: Springer Berlin Heidelberg
Electronic ISBN: 978-3-540-73510-6
Print ISBN: 978-3-540-73509-0
DOI: https://doi.org/10.1007/978-3-540-73510-6