Advances and Applications in Discrete Mathematics
Volume 17, Issue 1, Pages 1 - 9
(January 2016) http://dx.doi.org/10.17654/AADMJan2016_001_009 |
|
SOME REMARKS ON CENTRALITY IN THE SUBTREE GRAPH OF A TREE
Martti Hamina, Anneli Lankinen and Matti Peltola
|
Abstract: We consider the center problem in the subtree graph of a tree T. Let and be subtrees of a tree T. The subtree graph has the vertex set of all subtrees of T and two subtrees and are joined by an edge, if is obtained from the subtree by adding/removing a single vertex. A subtree S of a tree T is a central subtree of T if S has the minimum eccentricity in the subtree graph. The graph center of is the set of all central subtrees and a central subtree with the minimum number of vertices is a least central subtree of a tree T.
We compare different centrality concepts in We show that in the subtree graph, the branch weight center and distance center coincide and are isomorphic to some hypercube. Moreover, the least subtree within these centers is unique. |
Keywords and phrases: center, branch weight, distance sum, median graph, hypercube, joinsemilattice of subtrees, least central subtree, tree. |
|
Number of Downloads: 298 | Number of Views: 905 |
|