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 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
.
Acknowledgements
The authors are very grateful to the referees for their valuable comments and suggestions and to Professor Hongjiang Lai at West Virginia University for his carefully reading and modifying, which helped to improve the presentation of this paper.
Disclosure statement
No potential conflict of interest was reported by the authors.