ECCENTRICITY IN THE JOINSEMILATTICE GRAPH OF SUBTREES
Given a tree T, the subtree graph has vertex set of all subtrees of T, and two subtrees are joined by an edge if they differ by one vertex. A subtree U is a central subtree of T if U has the minimum eccentricity in We show that the eccentricity of a smallest central tree U is at most where is the number of the vertices of the tree U. The result leads to a new partition of trees into two classes. It will give a useful bound when constructing practical algorithms for least central subtrees. Moreover, we believe that it will give a mean for proving the exchange property for least central subtrees. Note that the exchange property will be true for solutions of the underlying minimax problem with tree restriction.
center, median semilattice, tree eccentricity, joinsemilattice of subtrees, least central subtree.