Maximizing the mean subtree order

Lucas Mol, Ortrud Oellermann

Published 2017-07-06Version 1

This article focuses on properties and structures of trees with maximum mean subtree order in a given family; such trees are called optimal in the family. For a fixed tree $Q$ with root vertex $v$, it is shown that among all trees obtained by gluing $v$ to a vertex of a path, the optimal tree occurs if $v$ is glued to a central vertex of the path. This result is used to determine optimal trees in several families, leads to a necessary condition on any optimal tree among all trees of a fixed order, and also provides an answer to an open problem of Jamison. Next, the family of all batons of a fixed order and the family of all bridges of a fixed order are considered, and the asymptotic structure of any optimal tree in each of these families is described. Finally, it is shown that any optimal tree among all trees of order $n$ has $\mathrm{O}(\log_2 n)$ leaves, and that any optimal tree among all caterpillars of order $n$ has $\Theta(\log_2 n)$ leaves.