2002-02.tur-etal
Graph Laplacians, Nodal Domains, and Hyperplane Arrangements
Abstract
Eigenvectors of the Laplacian of a graph G have received increasing
attention in the recent past. Here we investigate their so-called nodal
domains, i.e., the connected components of the maximal induced subgraphs of
G on which an eigenvector \psi does not change sign. An analogue of
Courant's nodal domain theorem provides upper bounds on the number of nodal
domains depending on the location of \psi in the spectrum. This bound,
however, is not sharp in general. In this contribution we consider the
problem of computing minimal and maximal numbers of nodal domains for a
particular graph. The class of Boolean Hypercubes is discussed in detail.
We find that, despite the simplicity of this graph class, for which
complete spectral information is available, the computations are still
non-trivial. Nevertheless, we obtained some new results and a number of
conjectures.
Mathematics Subject Classification:
58-99 (Global analysis, analysis on manifolds), 05C99 (Graph theory)
Key Words:
graph, graph Laplacian, discrete nodal domain theorem, eigenvectors, hyperplane arrangement, hypercube
Download Preprint
leydold@statistik.wu-wien.ac.at