pith. sign in

arxiv: math/0609475 · v1 · submitted 2006-09-17 · 🧮 math.CO

Enumeration of subtrees of trees

classification 🧮 math.CO
keywords subtreestreecharacterizeleastmaximumnumberweightsalgorithm
0
0 comments X
read the original 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 $\Delta$, which has the minimum number of subtrees.

This paper has not been read by Pith yet.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.