ELA, Volume 13, pp. 344-351, November 2005, abstract.
Nodal Domain Theorems and Bipartite Subgraphs
Turker Biyikoglu, Josef Leydold, and Peter Stadler
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. The number of strong nodal domains
is shown not to 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.