On subtrees of trees

L. A. Székely, Hua Wang

Research output: Contribution to journalArticlepeer-review

97 Scopus citations

Abstract

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). 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. Volk-mann, 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.

Original languageEnglish
Pages (from-to)138-155
Number of pages18
JournalAdvances in Applied Mathematics
Volume34
Issue number1
DOIs
StatePublished - Jan 2005

Scopus Subject Areas

  • Applied Mathematics

Keywords

  • Binary tree
  • Caterpillar
  • Center
  • Centroid
  • Multiple parsimony alignment with affine gap cost
  • Number of subtrees
  • Subtree core
  • Tree
  • Wiener index

Fingerprint

Dive into the research topics of 'On subtrees of trees'. Together they form a unique fingerprint.

Cite this