Inst. f. Informatik   
Uni Leipzig

Bioinformatics Preprint 05-022

[PostScript] [PDF]

Nodal Domain Theorems and Bipartite Subgraphs

Türker Biyikoglu, Josef Leydold, Peter F. 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. 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.

Keywords: Graph Laplacian, Nodal Domain Theorem, Eigenvectors, Bipartite Graphs

AMS: 05C50 Graphs and matrices, 05C22 Signed, gain and biased graphs, 05C83 Graph minors.

Return to 2005 working papers list.
Last modified: 2004-03-28 19:56:33 studla