Nodal Domain Theorems and Bipartite Subgraphs

Biyikoglu, Türker and Leydold, Josef and Stadler, Peter F. (2005) Nodal Domain Theorems and Bipartite Subgraphs. Preprint Series / Department of Applied Statistics and Data Processing, 55. Department of Statistics and Mathematics, Abt. f. Angewandte Statistik u. Datenverarbeitung, WU Vienna University of Economics and Business, Vienna.


Download (286kB)


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. (author's abstract)

Item Type: Paper
Keywords: graph theory / graph Laplacian / eigenvectors / nodal domain theorem / bipartite graphs
Classification Codes: MSC 05C50, 05C22, 05C83
Divisions: Departments > Finance, Accounting and Statistics > Statistics and Mathematics
Depositing User: Repository Administrator
Date Deposited: 10 Jul 2006 13:51
Last Modified: 22 Oct 2019 00:41


View Item View Item


Downloads per month over past year

View more statistics