Eigenvectors of Graph Laplacians

Research project P 14094 Eigenvectors of Graph Laplacians Josef Leydold 06.03.2000 The foundations of spectral graph theory were laid in the fifties and sixties. Since then, spectral methods have become standard techniques in (algebraic) graph theory. The eigenvalues of graphs mostly defined as the eigenvelues of the adjacency matrix, have received much attention over the last thirty years as means of characterizing classes of graphs and for obtaining bounds on the properties such as the diameter, girth, chromatic number, connectivity, etc. More recently, the interest has shifted somewhat from the adjaceny spectrum to the spectrum of the closely related graph Laplacian. Again, the dominating part of the theory is concerned with the eigenvalues. The eigenvectors of graphs, however, have received only sporadic attention on their own. Eigenvectors of graphs have been used to design heuristics for some combinatorial optimization problems such as graph partitioning, graph coloring or graph drawing. It turned out that the cost functions of a number of prominent combinatorial optimization problems, among TSP, are eigenfunctions of graphs associated with search heuristics for these problems. Surprisingly, it was only some years ago that the eigenvectors of graphs share some important properties with the eigenfunctions of Laplacian operators on Riemannian manifolds. This research project investigates the geometric features of eigenfunctions of discrete Laplacian operators depending on their location in the spectrum and depending on the structure of the underlying graph. One aim is a refinement of Courant`s nodal domain theorem, which states that an eigenfunction to the k-th eigenvalue (counting multiplicity) has a most k nodal domains, i.e., connected components of the respective subgraphs which non- positive and non-negative vertices. This bound is sharp only for a small number of graphs. We expect to obtain a better bond by means of, e.g., minors. Another topic is Faber-Krahn type inequalities. Here resulting graphs are similar but amazingly not equal to balls, as conjectured from the analogies to the classical Laplacian operator. Besides pure analytical work numerical experiments shall lead to conjectures or find counterexemples. Thus the development of an appropriate software tool is necessary.

Graphs are simple mathematical entities: Whenever we take single points (nodes) and connect them with lines (edges), we obtain a graph. A roadmap can serve as a simple example for that: The cities and road-crossings are the nodes, the reads themselves are the edges. This simple concept has multifarious applications in different fields. Besides the obvious modelling of transport- or telecommunication networks, the graphs are for instance also being used to yield descriptions of organic molecules or combinatorical problems. The study of the different properties of such graphs is the task of graph theory. One of the possible tools is the graph Laplacian. One can roughly imagine its effect in the following way: Imagining the nodes of the graph to resemble balls, being connected through springs along the edges. Whenever such a system is brought into oscillation by an impact, the motions of the single balls can be described by the graph Laplacian. The different modes of oscillation can be interpreted as being tones and overtones. In the present research project the different properties of such oscillating systems were studied. It turns out, that there are always points, which does not take part in the oscillations. One can cut the edges of the graph in exactly these points. The graph will thus disintegrate into different parts. As a result of the present project, it could be shown, that the possible number of parts cannot be arbitrary large. If we consider the kth mode of oscillation (overtone) then there can be at most k different parts and in many cases the number of different parts is even less. It is also interesting to see what happens when we make a drum out of such a graph by nailing some of its points onto a frame. The pitch arising from beating the drum is now seen dependent upon its size: the larger the drum, the lower the pitch. The pitch is also dependent upon the form. In real drums having equal areas the lowest pitch is found in the circular one. In graphs it is almost the same, but only almost since they have some additional angle somewhere. However, the analogy and picture with the drum is not far reaching enough. By the abstractness of the mathematical objects one is able to find connections to other different fields: like the traveling salesman problem, where a salesman attempts to visit all customers during the shortest possible round-trip; or to different questions from the theoretical biology.