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.