Enumeration of subtrees of trees
| dc.creator | Yan, Weigen | |
| dc.creator | Yeh, Yeong-Nan | |
| dc.date | 2006-09-17 | |
| dc.date.accessioned | 2026-07-07T07:24:54Z | |
| dc.date.available | 2026-07-07T07:24:54Z | |
| dc.description | 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. | |
| dc.description | 20 pages, 11 figures | |
| dc.identifier | https://arxiv.org/abs/math/0609475 | |
| dc.identifier | http://arxiv.org/abs/math/0609475 | |
| dc.identifier | doi:10.1016/j.tcs.2006.09.002 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/116546 | |
| dc.subject | Combinatorics | |
| dc.subject | 05C05 | |
| dc.title | Enumeration of subtrees of trees | |
| dc.type | text |