Maximizing the mean subtree order

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. Our main goal is to describe the structure of optimal trees in ${\mathcal{T}}_n$ and ${\mathcal{C}}_n$, the families of all trees and caterpillars, respectively, of order $n$. We begin by establishing a powerful tool called the Gluing Lemma, which is used to prove several of our main results. In particular, we show that if $T$ is an optimal tree in ${\mathcal{T}}_n$ or ${\mathcal{C}}_n$ for $n\ge 4$, then every leaf of $T$ is adjacent to a vertex of degree at least $3$. We also use the Gluing Lemma to answer an open question of Jamison, and to provide a conceptually simple proof of Jamison’s result that the path $P_n$ has minimum mean subtree order among all trees of order $n$. We prove that if $T$ is optimal in ${\mathcal{T}}_n$, then the number of leaves in $T$ is $\mathrm{O}({\log }_{2}n)$, and that if $T$ is optimal in ${\mathcal{C}}_n$, then the number of leaves in $T$ is $\mathrm{\Theta }({\log }_{2}n)$. Along the way, we describe the asymptotic structure of optimal trees in several narrower families of trees.