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\left(T\right)$ 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+2^{n-3}\le F\left(T\right)\le 2^{n-1}+n-1$.

KEYWORDS:

• Tree
• the number of subtrees
• diameter
• reliability
• network

2010 AMS SUBJECT CLASSIFICATIONS:

• 05C05
• 05C30

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.

Additional information

Funding

Research supported by the National Science Foundation of China [Nos. 61164005, 61440005, 11161037 and 11161074], the National Basic Research Program of China [No. 2010CB334708] and the Program for Changjiang Scholars and Innovative Research Team in Universities [No. IRT_15R40], and the Nature Science Foundation from Qinghai Province [Nos. 2014-ZJ-907 and 2014-ZJ-721]. The Research Fund for the Chunhui Program of Ministry of Education of China [No. Z2014022]. Key Laboratory of Tibetan Intelligent Information Processing and Machine Translation of Qinghai P.R.C [No.2013-Z-Y17].