zbMATH — the first resource for mathematics

The sum of the distances between the leaves of a tree and the ‘semi-regular’ property. (English) Zbl 1222.05027
Summary: Various topological indices have been put forward in different studies, from biochemistry to pure mathematics. Among them, the Wiener index, the number of subtrees, and the Randić index have received great attention from mathematicians. In the study of extremal problems regarding these indices among trees, one interesting phenomenon is that they share the same extremal tree structures. Much effort was devoted to the study of the correlations between these various indices. In this note we provide a common characteristic (the ‘semi-regular’ property) of these extremal structures, with respect to the above mentioned indices, among trees with a given maximum degree. This observation leads to a more unified approach for characterizing these extremal structures. As an application/example, we illustrate the idea by studying the extremal trees, regarding the sum of distances between all pairs of leaves of a tree, a new index, which recently appeared in phylogenetic tree reconstruction, and the study of the neighborhood of trees.

05C05 Trees
05C12 Distance in graphs
Full Text: DOI
[1] Allen, B.; Steel, M., Subtree transfer operations and their induced metrics on evolutionary trees, Ann. comb., 5, 1-15, (2001) · Zbl 0978.05023
[2] Delorme, C.; Favaron, O.; Rautenbach, D., On the randić index, Discrete math., 257, 29-38, (2002) · Zbl 1009.05075
[3] Dobrynin, A.A.; Entringer, R.; Gutman, I., Wiener index of trees: theory and applications, Acta appl. math., 66, 3, 211-249, (2001) · Zbl 0982.05044
[4] Fischermann, M.; Hoffmann, A.; Rautenbach, D.; Székely, L.A.; Volkmann, L., Wiener index versus maximum degree in trees, Discrete appl. math., 122, 1-3, 127-137, (2002) · Zbl 0993.05061
[5] P. Humphries, Combinatorial aspects of leaf-labelled trees, University of Canterbury, Ph.D. Thesis, 2008. http://hdl.handle.net/10092/1801.
[6] P. Humphries, T. Wu, On the neighborhood of trees (submitted for publication).
[7] Jelen, F.; Triesch, E., Superdominance order and distance of trees with bounded maximum degree, Discrete appl. math., 125, 2-3, 225-233, (2003) · Zbl 1009.05052
[8] Kirk, R.; Wang, H., Largest number of subtrees of trees with a given maximum degree, SIAM J. discrete math., 22, 3, 985-995, (2008) · Zbl 1180.05030
[9] Rautenbach, D., A note on trees of maximum weight and restricted degrees, Discrete math., 271, 335-342, (2003) · Zbl 1022.05013
[10] Semple, C.; Steel, M., Phylogenetics, (2003), Oxford University Press · Zbl 1043.92026
[11] Székely, L.A.; Wang, H., On subtrees of trees, Adv. in appl. math., 34, 138-155, (2005) · Zbl 1153.05019
[12] Wagner, S., Correlation of graph-theoretical indices, SIAM J. discrete math., 21, 1, 33-46, (2007) · Zbl 1144.05009
[13] Wang, H., The extremal values of the Wiener index of a tree with given degree sequence, Discrete appl. math., 156, 14, 2647-2654, (2008) · Zbl 1155.05020
[14] H. Wang, Sums of distances between vertices/leaves in \(k\)-ary trees, Bull. Inst. Combin. Appl. (in press). · Zbl 1223.05057
[15] Wiener, H., 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.