130
Views
15
CrossRef citations to date
0
Altmetric
Reviews

Trees with large numbers of subtrees

, , &
Pages 372-385 | Received 28 Dec 2014, Accepted 13 Oct 2015, Published online: 08 Dec 2015
 

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+2n3F(T)2n1+n1.

2010 AMS SUBJECT CLASSIFICATIONS:

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].

Reprints and Corporate Permissions

Please note: Selecting permissions does not provide access to the full text of the article, please see our help page How do I view content?

To request a reprint or corporate permissions for this article, please click on the relevant link below:

Academic Permissions

Please note: Selecting permissions does not provide access to the full text of the article, please see our help page How do I view content?

Obtain permissions instantly via Rightslink by clicking on the button below:

If you are unable to obtain permissions via Rightslink, please complete and submit this Permissions form. For more information, please visit our Permissions help page.