A service provided by the WU Library and the WU IT-Services

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 (241Kb) | Preview


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 13:50
Last Modified: 09 Aug 2015 12:38
URI: http://epub.wu.ac.at/id/eprint/1270


View Item