论文标题
根据树木的最大平均子树顺序
On the maximum mean subtree order of trees
论文作者
论文摘要
树的子树是再次是树（即连接）的任何诱导子图。树的平均子树序是其子树的平均顶点数量。贾米森（Jamison）在1980年代首次对这种不变性进行了分析。贾米森（Jamison）提出的一个有趣的公开问题询问，鉴于树的顺序，平均子树的最大命令的最大值是否总是由一些毛毛虫来实现。虽然我们没有完全解决这种猜想，但我们通过证明树木的不同特征来获得最大的特征来找到一些有利于它的证据。例如，我们表明，具有最大平均子树订单的订单$ n $树的直径必须非常接近$ n $。此外，我们表明最大平均子树订单等于$ n -2 \ log_2 n + o（1）$。对于本地均值子树订单，即包含固定顶点的所有子树的平均顺序，我们可以更加精确：我们证明其最大值始终是通过扫帚获得的，并且等于$ n- \ log_2 n + o（1）$。
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 - 2\log_2 n + 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 - \log_2 n + O(1)$.
