Split sizes and extremal tree shapes.

Abstract The size ‖ σ ‖ of a split σ (a bipartition) of the leaf set of a tree is the cardinality of the smaller part. There exist many studies of properties of the phylogenetic tree shapes (trees with no vertex of degree 2) and general trees related to the split sizes. A general function Φ f (T) = ∑ σ ∈ Σ ⁎ (T) f (‖ σ ‖) was proposed for an (strictly) increasing function f , where the sum is over all non-trivial splits induced by internal edges. There are many interesting applications of this important concept. In particular, Φ f (⋅) was used to measure the balance of phylogenetic tree shapes. Extremal problems for Φ f (⋅) have been considered and partially answered for binary trees. In this paper, we study the extremal trees with a given degree sequence that maximize or minimize Φ f (⋅). These results can also be directly applied to phylogenetic tree shapes and their degree sequences. When the number of leaves is fixed, we can also compare the extremal trees of different degree sequences. This comparison is conducted for degree sequences of phylogenetic tree shapes with given number of leaves. Immediate consequences are shown. Related problems are also proposed for potential future work. [ABSTRACT FROM AUTHOR]