Search CORE

8,988 research outputs found

On subtrees of trees

Author: Székely L.A.
Wang Hua
Publication venue
Publication date: 31/01/2005
Field of study

AbstractWe 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). Trees minimizing the total number of subtrees (or subtrees with at least one leaf) usually maximize the Wiener index, and vice versa. In [L.A. Székely, H. Wang, Binary trees with the largest number of subtrees, submitted for publication], 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 [L.A. Székely, H. Wang, Binary trees with the largest number of subtrees, submitted for publication] to binary trees maximizing the total number of subtrees with at least one leaf—this was first investigated by Knudsen [Lecture Notes in Bioinformatics, vol. 2812, Springer-Verlag, 2003, 433–446] 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 [L.A. Székely, H. Wang, Binary trees with the largest number of subtrees, submitted for publication] can be adapted to the minimization of Wiener index among binary trees, first solved in [M. Fischermann, A. Hoffmann, D. Rautenbach, L.A. Székely, L. Volkmann, Discrete Appl. Math. 122 (1–3) (2002) 127–137] and [F. Jelen, E. Triesch, Discrete Appl. Math. 125 (2-3) (2003) 225–233].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

Elsevier - Publisher Connector