A service provided by the WU Library and the WU IT-Services

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 (280Kb) | Preview


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 15:51
Last Modified: 11 Jun 2011 19:27
URI: http://epub.wu.ac.at/id/eprint/626


View Item