Extremal Trees with Respect to Dominance Order

Abstract

Let $(T_i{)}_{i\ge 0}$ be a sequence of trees such that $T_{i+1}$ arises by deleting the $b_i$ vertices of degree $\le 1$ from $T_i$. We determine those trees of given degree sequence or maximum degree for which the sequence $b_0,b_1,\dots$ is maximum or minimum with respect to the dominance order. As a consequence, we also determine trees of given degree sequence or maximum degree that are of maximum or minimum Balaban index.