zbMATH — the first resource for mathematics

On different “middle parts” of a tree. (English) Zbl 1393.05081
Summary: We determine the maximum distance between any two of the center, centroid, and subtree core among trees with a given order. Corresponding results are obtained for trees with given maximum degree and also for trees with given diameter. The problem of the maximum distance between the centroid and the subtree core among trees with given order and diameter becomes difficult. It can be solved in terms of the problem of minimizing the number of root-containing subtrees in a rooted tree of given order and height. While the latter problem remains unsolved, we provide a partial characterization of the extremal structure.

05C05 Trees
05C12 Distance in graphs
05C35 Extremal problems in graph theory
Full Text: Link
[1] E. Andriantiana, S. Wagner, and H. Wang. Greedy trees, subtrees and antichains. Electron. J. Combin., 20(3) #P28, 2013. · Zbl 1295.05076
[2] C.A. Barefoot, R.C. Entringer, and L.A. Sz´ekely. Extremal values for ratios of distances in trees. Discrete Appl. Math., 80:37-56, 1997. · Zbl 0886.05059
[3] R. Entringer, D. Jackson, and D. Snyder. Distance in graphs. Czechoslovak Math. J., 26:283-296, 1976. · Zbl 0329.05112
[4] R. Jamison. On the average number of nodes in a subtree of a tree. J. Combinatorial Theory Ser. B, 35:207-223, 1983. · Zbl 0509.05034
[5] C. Jordan. Sur les assemblages de lignes. J. Reine Angew. Math., 70:185-190, 1869. · JFM 02.0344.01
[6] L. Lov´asz. Combinatorial Problems and Exercises. AMS Chelsea Publishing, Providence, Rhode Island, 2 edition, 2007.
[7] N. Schmuck, S. Wagner, and H. Wang. Greedy trees, caterpillars, and wiener-type graph invariants. MATCH Commun. Math. Comput. Chem., 68:273-292, 2012. · Zbl 1289.05145
[8] L.A. Sz´ekely and H. Wang. On subtrees of trees. Adv. in Appl. Math., 34:138 - 155, 2005.
[9] L.A. Sz´ekely and H. Wang. Binary trees with the largest number of subtrees. Discrete Appl. Math., 155:374-385, 2007.
[10] H. Wang.The extremal values of the wiener index of a tree with given degree sequence. Discrete Appl. Math., 156:2647-2654, 2008. · Zbl 1155.05020
[11] H. Wiener. Structural determination of paraffin boiling points. J. Am. Chem. Soc., 69:17-20, 1947.
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.