Nodal Domain Theorems and Bipartite Subgraphs

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

Publikation: Working/Discussion PaperWU Working Paper

4 Downloads (Pure)

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. (author's abstract)
OriginalspracheEnglisch
ErscheinungsortVienna
HerausgeberDepartment of Statistics and Mathematics, Abt. f. Angewandte Statistik u. Datenverarbeitung, WU Vienna University of Economics and Business
PublikationsstatusVeröffentlicht - 2005

Publikationsreihe

NamePreprint Series / Department of Applied Statistics and Data Processing
Nr.55

WU Working Paper Reihe

  • Preprint Series / Department of Applied Statistics and Data Processing

Dieses zitieren