Some Structural Properties of a Least Central Subtree of a Tree

Authors

  • Martti Hamina University of Oulu
  • Matti Peltola University of Oulu

Abstract

We consider the graph center problem in the joinsemilattice L(T ) of all subtrees of a tree T . A subtree S of a tree T is a central subtree of T if S has the minimum eccentricity in the joinsemilattice. The graph center of the joinsemilattice is the set of all central subtrees. A central subtree with the minimum number of points is a least central subtree of a tree T . Thus least central subtrees of T are, in some sense, the best possible connected substructures of T among all connected substructures. We show that every tree is a unique least central subtree of some larger tree. Our main result points out the importance of the cardinality of the nodes of degree two. Low cardinality guarantees uniqueness and explicit construction for the least central subtree.

Downloads

How to Cite

Hamina, M., & Peltola, M. (2010). Some Structural Properties of a Least Central Subtree of a Tree. Algorithmic Operations Research, 5(2), Pages 105 – 118. Retrieved from https://journals.lib.unb.ca/index.php/AOR/article/view/18248

Issue

Vol. 5 No. 2 (2010)

Section

Articles

License

The copyright of the submitted article is hereby transferred to “Preeminent Academic Facets Inc. (the “publisher”) to the extent possible by the laws in the respective countries of the author(s). The author(s) retain all other rights including the following: 1. Any patents and trademark rights. 2. Right to post a pre-print version of the paper on the author’s personal website which is not used for commercial purposes. The author(s) warrant that the work is original, it has not been published elsewhere, it is not currently under consideration for publication in any form, and it does not infringe any copyright laws. The signing author or agent further warrants that all authors, if applicable, have been informed of the terms of this agreement and obtained the approval and authority to sign the agreement.