Enumeration of subtrees of trees

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.

20 pages, 11 figures

Cited by in corpus (13)

• Polynomially scaling spin dynamics simulation algorithm based on adaptive state space restriction
• Trees with given degree sequences that have minimal subtrees
• Enumerating the total number of subtrees of trees
• Graphs and unicyclic graphs with extremal number of connected induced subgraphs
• The shape of node reliability
• The core index of a graph
• Cut vertex and unicyclic graphs with the maximum number of connected induced subgraphs
• Further analysis on the total number of subtrees of trees
• Subtrees and BC-subtrees of maximum degree no more than k in trees
• The expected subtree number index in random polyphenylene and spiro chains
• Trees with the most subtrees -- an algorithmic approach
• Enumerating consistent subgraphs of directed acyclic graphs: an insight into biomedical ontologies
• The Number of Subtrees of Trees with Given Degree Sequence