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

Institute for Statistics and Mathematics

Publication: Working/Discussion Paper › WU Working Paper

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

Original language	English
Place of Publication	Vienna
Publisher	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
Publication status	Published - 2005

Publication series

Series	Preprint Series / Department of Applied Statistics and Data Processing
Number	55

WU Working Paper Series

Preprint Series / Department of Applied Statistics and Data Processing

Access to Document

10.57938/b1072f92-d08a-48d6-a908-3c717f8f9458Licence: Unspecified

DocumentFinal published version, 280 KBLicence: Unspecified

Check availability

University Library Catalogue

1 Journal article

Nodal Domain Theorems and Bipatite Subgraphs
Leydold, J., 2005, In: [Bitte Fachzeitschrift nachtragen.].
Publication: Scientific journal › Journal article › Research output without info reviewable/not-reviewable

Cite this

Biyikoglu, T., Leydold, J., & Stadler, P. F. (2005). Nodal Domain Theorems and Bipartite Subgraphs. (April 2005 ed.) 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 No. 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, no. 55, April 2005 edn, 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

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

Publication series

WU Working Paper Series

Access to Document

Check availability

Other versions

Nodal Domain Theorems and Bipatite Subgraphs

Cite this