Search

MiS Preprint Repository

We have decided to discontinue the publication of preprints on our preprint server as of 1 March 2024. The publication culture within mathematics has changed so much due to the rise of repositories such as ArXiV (www.arxiv.org) that we are encouraging all institute members to make their preprints available there. An institute's repository in its previous form is, therefore, unnecessary. The preprints published to date will remain available here, but we will not add any new preprints here.

MiS Preprint
73/2005

Nodal Domain Theorems and Bipartite Subgraphs

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

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.

Received:
Aug 2, 2005
Published:
Aug 2, 2005
MSC Codes:
05C50, 05C22, 05C83
Keywords:
graph laplacian, nodal domain theorem, eigenvectors, bipartite graphs

Related publications

inJournal
2005 Journal Open Access
Josef Leydold, Peter F. Stadler and Türker Biyikoglu

Nodal Domain Theorems and Bipartite Subgraphs

In: The electronic journal of linear algebra, 13 (2005), pp. 344-351