Balance vertices in trees

A new notion of balanced bipartitions of the vertices in a tree T is introd uced and studied. It gives rise to a new central set of vertices in T, each of which can be considered to be a discrete version of the center of gravi ty of T. We seek vertices x, called balance vertices, such that the two sum s of the distances from x to all the vertices in each of two subtrees of T are as equal as possible, where the two subtrees have only x in common, but , together, contain all the vertices of T. We discuss some of the computati on involved in a first step in determining the balance vertices. We prove t hat the median vertices, the center vertices, and the balance vertices may be arbitrarily far apart. We also prove that the set of balance vertices of a tree T consists of a single vertex or two adjacent vertices; the proof i nvolves a new type of "double orientation" of the edges of T. (C) 1999 John Wiley & Sons. Inc.