A discrete nodal domain theorem for trees
type: Item
instance of: scholarly article
title: A discrete nodal domain theorem for trees
zbMATH Open document ID: 1012.05114
DOI: 10.1016/S0024-3795(02)00451-2
published in: Linear Algebra and its Applications
publication date: 2003-03-11T00:00:00Z
review text: consider a graph \(G\) on vertices \(1,2,\dots,n\) and a real vector \((x_1,x_2,\dots,x_n)\). A positive (negative) sign graph is a maximal connected subgraph of \(G\) on vertices \(v\) with \(x_v>0\) (\(x_v<0\)). Sign graphs are also called nodal domains. Their number is denoted by \(\eta(x)\). Let \(A\) be a generalized Laplacian of \(G\), that is \(A\) is a symmetric \(n \times n\) matrix and its entries are negative for adjacent vertices and zero for distinct non-adjacent vertices. Consider the eigenvalues \(\lambda_1 \leq \lambda_2 \leq \dots \leq \lambda_n\) of \(A\). \textit{E. B. Davies} et al.\ [Linear Algebra Appl.\ 336, 51-60 (2001; Zbl 0990.05093)] proved that \(\eta(y) \leq k+r-1\) for all eigenvectors \(y\) of \(A\) corresponding with an eigenvalue \(\lambda_k\) of multiplicity \(r\). This discrete nodal domain theorem is strengthened for trees. If \(G\) is a tree and \(y\) is an eigenvector without a vanishing coordinate, then the corresponding eigenvalue \(\lambda_k\) is simple and \(\eta(y)=k\). For multiple eigenvalues more complicated bounds exist. Given a generalized Laplacian \(A\) of a tree and an eigenvalue \(\lambda\) of \(A\) with multiplicity at least \(2\), a corresponding eigenvector \(y\) with maximal \(\eta(y)\) can be found in time \(O(n^2)\). Deciding the corresponding minimization problem is NP-complete.
Mathematics Subject Classification ID: 05C50
Mathematics Subject Classification ID: 05C05
Mathematics Subject Classification ID: 05C22
Mathematics Subject Classification ID: 68R10
zbMATH DE Number: 1880035
zbMATH Keywords: discrete nodal domain theorem
zbMATH Keywords: tree
zbMATH Keywords: sign graph
zbMATH Keywords: graph Laplacian
author: Türker Bıyıkoğlu
MaRDI profile type: Publication
cites work: Discrete nodal domain theorems
cites work: Permanental roots and the star degree of a graph
cites work: Eigenvectors of acyclic matrices
cites work: Q4198056
cites work: On the eigenvectors belonging to the minimum eigenvalue of an essentially nonnegative symmetric matrix with bipartite graph
Recommended article: Q5469422
Recommended article: Graph Laplacians, nodal domains, and hyperplane arrangements
Recommended article: Nodal decompositions of graphs
Recommended article: Perron-Frobenius type results and discrete versions of nodal domain theorems
Recommended article: Graphs and their real eigenvectors
Recommended article: Minimum vertex covers and the spectrum of the normalized Laplacian on trees
Recommended article: Q4710059
Recommended article: A sharp upper bound on the least signless Laplacian eigenvalue using domination number
Recommended article: Symmetric matrices, signed graphs, and nodal domain theorems
Recommended article: Nodal domain and eigenvalue multiplicity of graphs
description: scientific article; zbMATH DE number 1880035