Research confirms minimum mean subtree order occurs in paths, discussing proof for maximum in cliques.
It has been conjectured that the minimum and maximum of the mean subtree order among connected graphs of order n are attained by the path Pₙ and clique Kₙ, respectively. Extending ideas due to Haslegrave and Vince, we confirm that the minimum is indeed attained by Pₙ. On the other hand, we discuss different approaches (both promising and flawed) that could lead to a proof of the extremality of Kₙ.
No takes yet. Share an insight, caveat, or question.
Cambie et al. (2025) studied this question.
Synapse has enriched 5 closely related papers on similar clinical questions. Consider them for comparative context: