IMI Interdisciplinary Mathematics InstituteCollege of Arts and Sciences

On subtrees of trees


A 2004 Preprint by L. Székely and H. Wang

  • 2004:04
  • We study that over a certain type of trees (e.g. all trees or all binary trees) with a given number of vertices, which trees minimize or maximize the total number of subtrees (or subtrees with at least one leaf). 'frees minimizing the total number of subtrees (or subtrees with at least one leaf) usually maximize the Wiener index, and vice versa. In [10], we described the structure of binary trees maximizing the total number of subtrees, here we provide a formula for this maximum value. We extend here the results from [10] to binary trees maximizing the total number of subtrees with at least one leaf-this was first investigated by Knudsen [8] to provide upper bound for the time complexity of his multiple parsimony alignment with affine gap cost using a phylogenetic tree.

    Also, we show that the techniques of [10] can be adapted to the minimization of Wiener index among binary trees, first solved in [5] and [6]. Using the number of subtrees containing a particular vertex, we define the subtree core of the tree, a new concept analogous to, but different from the concepts of center and centroid.

© Interdisciplinary Mathematics Institute | The University of South Carolina Board of Trustees | Webmaster
USC