Trees with large numbers of subtrees

Abstract

The number of subtrees in a graph is related to the reliability of a network with possible vertex failure and edge failure. It is known that networks with larger number of subtrees would be more reliable. Therefore, for given families of graphs, determining the graphs with maximum number of subtrees within the family becomes important. For a tree T of n vertices, let F(T) denote the number of all subtrees in T. Yan and Yeh gave a linear-time algorithm to count the number of subtrees in T and determined the tree of diameter d and order n with the maximum number of subtrees. In this paper, we present two recursive relations to count the number of subtrees of trees. We also characterize all trees of n vertices with 5+n+2n−3≤F(T)≤2n−1+n−1.