Nodal Domain Theorems and Bipartite Subgraphs

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

doi:10.57938/b1072f92-d08a-48d6-a908-3c717f8f9458

Nodal Domain Theorems and Bipartite Subgraphs

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

Statistics and Mathematics

Publikation: Working/Discussion Paper › WU Working Paper und Case

47 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)

Originalsprache	Englisch
Erscheinungsort	Vienna
Herausgeber	Department of Statistics and Mathematics, Abt. f. Angewandte Statistik u. Datenverarbeitung, WU Vienna University of Economics and Business
DOIs	https://doi.org/10.57938/b1072f92-d08a-48d6-a908-3c717f8f9458
Publikationsstatus	Veröffentlicht - 2005

Publikationsreihe

Reihe	Preprint Series / Department of Applied Statistics and Data Processing
Nummer	55

WU Working Papers und Cases

Preprint Series / Department of Applied Statistics and Data Processing

Zugriff auf Dokument

10.57938/b1072f92-d08a-48d6-a908-3c717f8f9458Lizenz: Nicht angegeben

DocumentEndgültige, publizierte Fassung, 280 KBLizenz: Nicht angegeben

1 Originalbeitrag in Fachzeitschrift

Nodal Domain Theorems and Bipatite Subgraphs
Leydold, J., 2005, in: [Bitte Fachzeitschrift nachtragen.].
Publikation: Wissenschaftliche Fachzeitschrift › Originalbeitrag in Fachzeitschrift › Publikationen ohne Kategorie begutachtet/nicht begutachtet

Zitat

Biyikoglu, T., Leydold, J., & Stadler, P. F. (2005). Nodal Domain Theorems and Bipartite Subgraphs. (April 2005 Aufl.) Department of Statistics and Mathematics, Abt. f. Angewandte Statistik u. Datenverarbeitung, WU Vienna University of Economics and Business. Preprint Series / Department of Applied Statistics and Data Processing Nr. 55 https://doi.org/10.57938/b1072f92-d08a-48d6-a908-3c717f8f9458

@techreport{b1072f92d08a48d6a9083c717f8f9458,

title = "Nodal Domain Theorems and Bipartite Subgraphs",

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)",

author = "T{\"u}rker Biyikoglu and Josef Leydold and Stadler, \{Peter F.\}",

year = "2005",

doi = "10.57938/b1072f92-d08a-48d6-a908-3c717f8f9458",

language = "English",

series = "Preprint Series / Department of Applied Statistics and Data Processing",

number = "55",

publisher = "Department of Statistics and Mathematics, Abt. f. Angewandte Statistik u. Datenverarbeitung, WU Vienna University of Economics and Business",

edition = "April 2005",

type = "WorkingPaper",

institution = "Department of Statistics and Mathematics, Abt. f. Angewandte Statistik u. Datenverarbeitung, WU Vienna University of Economics and Business",

}

Biyikoglu, T, Leydold, J & Stadler, PF 2005 'Nodal Domain Theorems and Bipartite Subgraphs' Preprint Series / Department of Applied Statistics and Data Processing, Nr. 55, April 2005 Aufl., Department of Statistics and Mathematics, Abt. f. Angewandte Statistik u. Datenverarbeitung, WU Vienna University of Economics and Business, Vienna. https://doi.org/10.57938/b1072f92-d08a-48d6-a908-3c717f8f9458

TY - UNPB

T1 - Nodal Domain Theorems and Bipartite Subgraphs

AU - Biyikoglu, Türker

AU - Leydold, Josef

AU - Stadler, Peter F.

PY - 2005

Y1 - 2005

N2 - 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)

AB - 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)

U2 - 10.57938/b1072f92-d08a-48d6-a908-3c717f8f9458

DO - 10.57938/b1072f92-d08a-48d6-a908-3c717f8f9458

M3 - WU Working Paper and Case

T3 - Preprint Series / Department of Applied Statistics and Data Processing

BT - Nodal Domain Theorems and Bipartite Subgraphs

PB - Department of Statistics and Mathematics, Abt. f. Angewandte Statistik u. Datenverarbeitung, WU Vienna University of Economics and Business

CY - Vienna

ER -

Nodal Domain Theorems and Bipartite Subgraphs

Abstract

Publikationsreihe

WU Working Papers und Cases

Zugriff auf Dokument

Publikationen

Nodal Domain Theorems and Bipatite Subgraphs

Zitat