2005-04.biy-ley-pfs
#
Nodal Domain Theorems and Bipartite Subgraphs

### Abstract

The Discrete Nodal Domain Theorem states that an eigenfunction of the
*k*-th largest eigenvalue of a generalized graph Laplacian has at most *k*
(weak) nodal domains. We show that the number of strong nodal domains
cannot exceed the size of a maximal induced bipartite subgraph and that
this bound is sharp for generalized graph Laplacians. Similarly, the number
of weak nodal domains is bounded by the size of a maximal bipartite minor.

**Mathematics Subject Classification:**
05C50 Graphs and matrices,
05C22 Signed, gain and biased graphs,
05C83 Graph minors

**Key Words:**
graph theory, graph Laplacian,
eigenvectors, nodal domain theorems,bipartite graphs

Download Preprint
[ Postscript | PDF ]

Josef.Leydold@statistik.wu-wien.ac.at