
details
Title
Optimizing quadratic forms of adjacency matrices of trees
Abstract Let G=(V,E) be a tree with n vertices. For n nonnegative numbers
x1>= x2 ... >= xn>= 0,
there exists a mapping \sigma: V > {x1,...,xn} which maximizes $\sum \sigma(v)\sigma(w)$, where the sum is over all the edges (v,w) of G . A necessary and sufficient condition is determined for \sigma to be independent of the choice of xi's, and it leads to a corresponding solution for the following problem: Maximize the largest eigenvalue of PDPt+A over a permutation matrix P, where D is a nonnegative diagonal matrix and A is the adjacency matrix of a tree.
Speaker(s)
WaiShun Cheung (Centro de Estruturas Lineares e Combinatórias, Universidade de Lisboa, Portugal)
Date
May 22, 2002 Time 15:00 Room
Sala 5.5

