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