Resource title

A Discrete Nodal Domain Theorem for Trees

Resource image

image for OpenScout resource :: A Discrete Nodal Domain Theorem for Trees

Resource description

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) ; Series: Preprint Series / Department of Applied Statistics and Data Processing

Resource author

Türker Biyikoglu

Resource publisher

Resource publish date

Resource language


Resource content type


Resource resource URL

Resource license

Adapt according to the license agreement. Always reference the original source and author.