Definition of an imbalance index

A function t:\mathcal{T}^\ast (\mathcal{BT}^\ast) \rightarrow \mathbb{R} is called a (rooted binary) tree shape statistic (TSS) if t(T) depends only on the shape of T and not on the labeling of vertices or the lengths of edges. Now, we can define tree imbalance indices as follows:

A (binary) tree shape statistic t is called an imbalance index if and only if

  • the caterpillar tree T^{cat} is the unique tree maximizing t on \mathcal{T}_n^\ast(\mathcal{BT}_n^\ast) for all n\geq 1,
  • and the fully balanced tree T^{fb} is the unique tree minimizing t on \mathcal{BT}_n^\ast for all n=2^h with h\in\mathbb{N}_{\geq 0}.

Here, \mathcal{T}_n^\ast denotes the set of arbitrary rooted trees with n leaves and \mathcal{BT}_n^\ast denotes the set of rooted binary trees with n leaves.

Imbalance indices