A Discrete Nodal Domain Theorem for Trees

Türker Biyikoglu

Publikation: Working/Discussion PaperWU Working Paper

Abstract

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)
OriginalspracheEnglisch
ErscheinungsortVienna
HerausgeberDepartment of Statistics and Mathematics, Abt. f. Angewandte Statistik u. Datenverarbeitung, WU Vienna University of Economics and Business
PublikationsstatusVeröffentlicht - 2002

Publikationsreihe

NamePreprint Series / Department of Applied Statistics and Data Processing
Nr.43

WU Working Paper Reihe

  • Preprint Series / Department of Applied Statistics and Data Processing

Dieses zitieren