×

On the maximum value of the stairs2 index. (English) Zbl 07904786

Summary: Measures of tree balance play an important role in different research areas such as mathematical phylogenetics or theoretical computer science. The balance of a tree is usually quantified in a single number, called a balance or imbalance index, and several such indices exist in the literature. Here, we focus on the stairs2 balance index for rooted binary trees, which was first introduced in the context of viral phylogenetics but has not been fully analyzed from a mathematical viewpoint yet. While it is known that the caterpillar tree uniquely minimizes the stairs2 index for all leaf numbers and the fully balanced tree uniquely maximizes the stairs2 index for leaf numbers that are powers of two, understanding the maximum value and maximal trees for arbitrary leaf numbers has been an open problem in the literature. In this note, we fill this gap by showing that for all leaf numbers, there is a unique rooted binary tree maximizing the stairs2 index. Additionally, we obtain recursive and closed expressions for the maximum value of the stairs2 index of a rooted binary tree with \(n\) leaves.

MSC:

05C05 Trees
05C35 Extremal problems in graph theory

References:

[1] Bartoszek, K.; Coronado, T. M.; Mir, A.; Rosselló, F., Squaring within the Colless index yields a better balance index, Math. Biosci., 331, Article 108503 pp., Jan. 2021 · Zbl 1457.92123
[2] Blum, M. G.; François, O., On statistical tests of phylogenetic tree imbalance: the Sackin and other indices revisited, Math. Biosci., 195, 2, 141-153, June 2005 · Zbl 1065.62183
[3] Colijn, C.; Gardy, J., Phylogenetic tree shapes resolve disease transmission patterns, Evol. Med. Public Health, 2014, 1, 96-108, Jan. 2014
[4] Colless, D., Review of “Phylogenetics: the theory and practice of phylogenetic systematics”, Syst. Zool., 31, 1, 100-104, 1982, (ISSN 00397989.)
[5] Coronado, T. M.; Mir, A.; Rosselló, F.; Valiente, G., A balance index for phylogenetic trees based on rooted quartets, J. Math. Biol., 79, 3, 1105-1148, June 2019 · Zbl 1416.05069
[6] Coronado, T. M.; Mir, A.; Rosselló, F.; Rotger, L., On Sackin’s original proposal: the variance of the leaves’ depths as a phylogenetic balance index, BMC Bioinform., 21, 1, Apr. 2020
[7] Fischer, M.; Herbst, L.; Kersting, S.; Kühn, A. L.; Wicke, K., Tree Balance Indices: A Comprehensive Survey, Nov. 2023, Springer International Publishing: Springer International Publishing Cham, Switzerland · Zbl 1529.05001
[8] Kersting, S. J.; Fischer, M., Measuring tree balance using symmetry nodes — a new balance index and its extremal properties, Math. Biosci., 341, Article 108690 pp., Nov. 2021 · Zbl 1480.92148
[9] Khurana, M. P.; Scheidwasser-Clow, N.; Penn, M. J.; Bhatt, S.; Duchêne, D. A., The limits of the constant-rate birth-death prior for phylogenetic tree topology inference, Syst. Biol., 73, 1, 235-246, Dec. 2023
[10] McKenzie, A.; Steel, M., Distributions of cherries for two models of trees, Math. Biosci., 164, 1, 81-92, Mar. 2000 · Zbl 0947.92021
[11] Mir, A.; Rosselló, F.; Rotger, L., A new balance index for phylogenetic trees, Math. Biosci., 241, 1, 125-136, Jan. 2013 · Zbl 1303.92084
[12] Norström, M. M.; Prosperi, M. C.; Gray, R. R.; Karlsson, A. C.; Salemi, M., PhyloTempo: a set of R scripts for assessing and visualizing temporal clustering in genealogies inferred from serially sampled viral sequences, Evol. Bioinform., 8, Article EBO.S9738 pp., Jan. 2012
[13] Rogers, J. S., Central moments and probability distributions of three measures of phylogenetic tree imbalance, Syst. Biol., 45, 1, 99-110, Mar. 1996
[14] Sackin, M. J., “Good“ and “bad” phenograms, Syst. Biol., 21, 2, 225-226, 1972
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.