Nodal Domain Theorems and Bipartite Subgraphs

Türker Biyikoglu, Josef Leydold, and Peter F. Stadler

Contact the author: Please use for correspondence this email.
Submission date: 02. Aug. 2005 (revised version: August 2005)
Pages: 10
published in: The electronic journal of linear algebra, 13 (2005), p. 344-351 
DOI number (of the published article): 10.13001/1081-3810.1167
Bibtex
MSC-Numbers: 05C50, 05C22, 05C83
Keywords and phrases: graph laplacian, nodal domain theorem, eigenvectors, bipartite graphs
Download full preprint: PDF (170 kB), PS ziped (204 kB)

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.