Advances and Applications in Discrete Mathematics
Volume 13, Issue 2, Pages 117 - 142
(April 2014)
|
|
ECCENTRICITY IN THE JOINSEMILATTICE GRAPH OF SUBTREES
Martti Hamina, Anneli Lankinen and Matti Peltola
|
Abstract: 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. |
Keywords and phrases: center, median semilattice, tree eccentricity, joinsemilattice of subtrees, least central subtree. |
|
Number of Downloads: 225 | Number of Views: 868 |
|