  The minimum height of vertex and edge partition trees are well-studied graph
parameters known as, for instance, vertex and edge ranking number. While they
are NP-hard to determine in general, linear-time algorithms exist for trees.
Motivated by a correspondence with Dasgupta's objective for hierarchical
clustering we consider the total rather than maximum depth of vertices as an
alternative objective for minimization. For vertex partition trees this leads
to a new parameter with a natural interpretation as a measure of robustness
against vertex removal.
  As tools for the study of this family of parameters we show that they have
similar recursive expressions and prove a binary tree rotation lemma. The new
parameter is related to trivially perfect graph completion and therefore
intractable like the other three are known to be. We give polynomial-time
algorithms for both total-depth variants on caterpillars and on trees with a
bounded number of leaf neighbors. For general trees, we obtain a
2-approximation algorithm.
