The Number of Subtrees in Trees  
 

László A. Székely and Hua Wang

Department of Mathematics, University of South Carolina, Columbia SC 29208, U.S.A.

szekely@math.sc.edu  hwang0@math.sc.edu

Abstract.      Full Text 1 PDF     Full Text 2 PDF

Consider in any given tree the number of subtrees containing a particular vertex. This function, defined on vertices, is maximized in a single vertex or in two adjacent vertices, that we call the subtree core of the tree. This provides a new concept for the “middle” of the tree, which is analogous to, but differs from the concepts of center and centroid.

We study the total number of subtrees of a tree from an extremal combinatorics point of view: over a certain type of trees (e.g. all trees or all binary trees) with a given number of vertices or leaves, which trees minimize or maximize the total number of subtrees.

We describe the structure of binary trees maximizing the total number of subtrees. The same structure was found by Fischermann, Hoffmann, Rautenbach, Székely, and Volkmann, and also by Jelen and Triesch, as the structure minimizing the Wiener index. We also provide a closed form for this maximum value, for any fixed number of leaves, using a new alternative binary representation of integers. This maximum value is of interest, since Knudsen used this quantity to provide upper bound for the time complexity of his multiple parsimony alignment with affine gap cost using a phylogenetic tree.

We make a surprising observation, that the trees minimizing the total number of subtrees usually maximize the Wiener index, and vice versa. However, we provide examples showing that this fact cannot be explained through a monotone relationship between the total number of subtrees and the Wiener index valid for all trees.

---

 * This research was supported in part by the NSF contracts DMS 007 2187 and
0302307.