TY - JOUR

T1 - On the maximum value of the stairs2 index

AU - Currie, Bryan

AU - Wicke, Kristina

N1 - Publisher Copyright:
© 2024 Elsevier Inc.

PY - 2024/8

Y1 - 2024/8

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

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

KW - Binary echelon tree

KW - Phylogenetic tree balance

KW - stairs2 index

UR - http://www.scopus.com/inward/record.url?scp=85196820119&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85196820119&partnerID=8YFLogxK

U2 - 10.1016/j.aam.2024.102732

DO - 10.1016/j.aam.2024.102732

M3 - Article

AN - SCOPUS:85196820119

SN - 0196-8858

VL - 159

JO - Advances in Applied Mathematics

JF - Advances in Applied Mathematics

M1 - 102732

ER -