Enumeration of subtrees of trees

Weigen Yan; Yeong-Nan Yeh

doi:10.1016/j.tcs.2006.09.002

paper

Enumeration of subtrees of trees

arXiv:math/0609475 · doi:10.1016/j.tcs.2006.09.002

Abstract

Let $T$ be a weighted tree. The weight of a subtree $T_{1}$ of $T$ is defined as the product of weights of vertices and edges of $T_{1}$ . We obtain a linear-time algorithm to count the sum of weights of subtrees of $T$ . As applications, we characterize the tree with the diameter at least $d$ , which has the maximum number of subtrees, and we characterize the tree with the maximum degree at least $Δ$ , which has the minimum number of subtrees.

20 pages, 11 figures