Abstract
In this paper, we investigate the structures of extremal trees which have the minimal number of subtrees in the set of all trees with a given degree sequence. In particular, the extremal trees must be caterpillar and but in general not unique. Moreover, all extremal trees with a given degree sequence \({\pi = (d_1, \ldots, d_{5}, 1, \ldots, 1)}\) have been characterized.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Agra A., Gouveia L., Requejo C.: Extended formulations for the cardinality constrained subtree of a tree problem. Oper. Res. Lett. 37, 192–196 (2009)
Bondy J.A., Murty U.S.R.: Graph theory with applications. Macmillan Press, New York (1976)
Çela E., Schmuck N.S., Wimer S., Woeginger G.J.: The Wiener maximum quadratic assignment problem. Discrete Optim. 8, 411–416 (2011)
Eisenstat D., Gordon G.: Non-isomorphic caterpillars with identical subtree data. Discrete Math. 306, 827–830 (2006)
Heuberger C., Prodinger H.: On α-greedy expansions of numbers. Adv. Appl Math. 38, 505–525 (2007)
Kirk R., Wang H.: Largest number of subtrees of trees with a given maximum degree. SIAM J. Discrete Math. 22, 985–995 (2008)
Knudsen, B.: Optimal multiple parsimony alignment with affine gap cost using a phylogenetic tree. In: Lecture Notes in Bioinformatics, vol. 2812, pp. 433–446. Springer, Berlin (2003)
Meir A., Moon J.W.: On subtrees of certain families of rooted trees. Ars. Combin. 16, 305–318 (1983)
Shi R.: The average distance of trees. Syst. Sci. Math. Sci. 6(1), 18–24 (1993)
Székely L.A., Wang H.: On subtrees of trees. Adv. Appl. Math. 34, 138–155 (2005)
Székely L.A., Wang H.: Binary trees with the largest number of subtrees with at least one leaf. Congr Numer. 177, 147–169 (2005)
Székely L.A., Wang H.: Binary trees with the largest number of subtrees. Discrete Appl. Math. 155, 374–385 (2007)
Székely L.A., Wang H., Wu T.Y.: The sum of the distances between the leaves of a tree and the “semi-regular” property. Discrete Math. 311, 1197–1203 (2011)
Vince A., Wang H.: The average order of a subtree of a tree. J. Combin. Theory Ser. B. 100, 161–170 (2010)
Wagner S.G.: Correlation of graph-theoretical indeces. SIAM J. Discrete Math. 21, 33–46 (2007)
Wang H.: The extremal values of the Wiener index of a tree with given degree sequence. Discrete Appl Math. 156, 2647–2654 (2008)
Wiener H.: Structural determination of paraffin boiling poiling points. J. Am. Chem. Soc. 69, 17–20 (1947)
Yan W.G., Yeh Y.N.: Enumeration of subtrees of trees. Theoret. Comput. Sci. 369, 256–268 (2006)
Zhang X.D., Xiang Q.Y., Xu L.Q., Pan R.Y.: The Wiener Index of trees with given degree sequences. MATCH Commun. Math. Comput. Chem. 60, 623–644 (2008)
Zhang X.D., Liu Y., Han M.X.: Maximum Wiener index of trees with given degree sequence. MATCH Commun. Math. Comput. Chem. 64, 661–682 (2010)
Zhang X.M., Zhang X.D., Gray D., Wang H.: Trees with the most subtrees—an algorithmic approach. J. Combin. 3(2), 207–223 (2012)
Zhang, X.M., Zhang, X.D., Gray, D., Wang H.: The number of subtrees with given degree sequence. J. Graph Theory 73, 280–295 (2013)
Author information
Authors and Affiliations
Corresponding author
Additional information
This work is supported by the National Natural Science Foundation of China (No.11271256), Innovation Program of Shanghai Municipal Education Commission (No.14ZZ016), Specialized Research Fund for the Doctoral Program of Higher Education (No.20130073110075), and the Research Foundation for important professional in voluntary university (No:Z-2204-11092).
Rights and permissions
About this article
Cite this article
Zhang, XM., Zhang, XD. The Minimal Number of Subtrees with a Given Degree Sequence. Graphs and Combinatorics 31, 309–318 (2015). https://doi.org/10.1007/s00373-013-1383-z
Received:
Revised:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00373-013-1383-z