TBI 02-tb-001
A Discrete Nodal Domain Theorem for Trees
02-tb-001
Abstract:
A Discrete Nodal Domain Theorem for Trees
[PostScript]
[PDF]
T. Biyikoglu
Let G be a connected graph with n vertices and let
x=(x_1,...,x_n) be a real vector. A positive (negative) sign graph
of the vector x is a maximal connected subgraph of G on
vertices x_i>0 (x_i<0). For an eigenvalue of a
generalized Laplacian of a tree: We character ize the maximal number of
sign graphs of an eigenvector. We give an O(n^2) 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.
Keywords:
discrete nodal domain theorem;
eigenvectors of a matrix with non-positive off-diagonal elements;
tree;
graph Laplacian;
Return to 2002 working papers list.