A Discrete Nodal Domain Theorem for Trees

Biyikoglu, Türker (2002) A Discrete Nodal Domain Theorem for Trees. Preprint Series / Department of Applied Statistics and Data Processing, 43. Department of Statistics and Mathematics, Abt. f. Angewandte Statistik u. Datenverarbeitung, WU Vienna University of Economics and Business, Vienna.


Download (247kB)


Let G be a connected graph with n vertices and let x=(x1, ..., xn) be a real vector. A positive (negative) sign graph of the vector x is a maximal connected subgraph of G on vertices xi>0 (xi<0). For an eigenvalue of a generalized Laplacian of a tree: We characterize the maximal number of sign graphs of an eigenvector. We give an O(n2) time algorithm to find an eigenvector with maximum number of sign graphs and we show that finding an eigenvector with minimum number of sign graphs is an NP-complete problem. (author's abstract)

Item Type: Paper
Additional Information: published in: Linear Algebra and its Applications 360, pp. 197-205, 2003
Keywords: graph / discrete nodal domain theorem / eigenvectors of a matrix with non-positive off-diagonal elements / tree / graph Laplacian / Sign graph
Classification Codes: MSC 58-99, 05C99
Divisions: Departments > Finance, Accounting and Statistics > Statistics and Mathematics
Depositing User: Repository Administrator
Date Deposited: 10 Jul 2006 11:50
Last Modified: 22 Oct 2019 00:41
URI: https://epub.wu.ac.at/id/eprint/1270


View Item View Item


Downloads per month over past year

View more statistics