PC Seminar: Extrema of the mean subtree order of graphs

Abstract:

Consider all (not necessarily induced) subtrees of a graph G. The mean subtree order of G is the average number of vertices in such a subtree. Among all connected graphs with n vertices, the path has the smallest mean subtree order, while the complete graph has the largest. These simple statements are surprisingly difficult to prove, as some natural approaches fail. In this talk, I will particularly focus on the proof for the maximum, which involves results on random trees in a surprising way.

Joint work with Stijn Cambie and Jorik Jooken