TY - JOUR

T1 - On the maximum mean subtree order of trees

AU - Cambie, Stijn

AU - Wagner, Stephan

AU - Wang, Hua

N1 - Publisher Copyright:
© 2021 The Author(s)

PY - 2021/10

Y1 - 2021/10

N2 - A subtree of a tree is any induced subgraph that is again a tree (i.e., connected). The mean subtree order of a tree is the average number of vertices of its subtrees. This invariant was first analyzed in the 1980s by Jamison. An intriguing open question raised by Jamison asks whether the maximum of the mean subtree order, given the order of the tree, is always attained by some caterpillar. While we do not completely resolve this conjecture, we find some evidence in its favor by proving different features of trees that attain the maximum. For example, we show that the diameter of a tree of order n with maximum mean subtree order must be very close to n. Moreover, we show that the maximum mean subtree order is equal to n−2log2n+O(1). For the local mean subtree order, which is the average order of all subtrees containing a fixed vertex, we can be even more precise: we show that its maximum is always attained by a broom and that it is equal to n−log2n+O(1).

AB - A subtree of a tree is any induced subgraph that is again a tree (i.e., connected). The mean subtree order of a tree is the average number of vertices of its subtrees. This invariant was first analyzed in the 1980s by Jamison. An intriguing open question raised by Jamison asks whether the maximum of the mean subtree order, given the order of the tree, is always attained by some caterpillar. While we do not completely resolve this conjecture, we find some evidence in its favor by proving different features of trees that attain the maximum. For example, we show that the diameter of a tree of order n with maximum mean subtree order must be very close to n. Moreover, we show that the maximum mean subtree order is equal to n−2log2n+O(1). For the local mean subtree order, which is the average order of all subtrees containing a fixed vertex, we can be even more precise: we show that its maximum is always attained by a broom and that it is equal to n−log2n+O(1).

UR - http://www.scopus.com/inward/record.url?scp=85110234891&partnerID=8YFLogxK

U2 - 10.1016/j.ejc.2021.103388

DO - 10.1016/j.ejc.2021.103388

M3 - Article

AN - SCOPUS:85110234891

SN - 0195-6698

VL - 97

JO - European Journal of Combinatorics

JF - European Journal of Combinatorics

M1 - 103388

ER -