Logo: to the web site of Uppsala University

Given a tree T and a subtree S of T, one can define the local mean at S, μ_T(S),to be the average order of the subtrees of T containing S. In 1983, Jamison showed that μ_T(S)< μ_T(S′) if S ⊂ S′ as subtrees of T. Therefore, it is natural to ask the following question. Among all the k-subtrees (subtrees of order k), which one achieves the maximal/minimal local mean and what properties does it have? We call such k-subtrees k-maximal/k-minimal. Wagner and H. Wang showed in 2016t hat a 1-maximal subtree has degree 1 or 2. In this paper, we show that if T is not a path, a 1-minimal subtree of T has degree at least 3. For  k≥2, we show that a  k-maximal subtree has at most one leaf whose degree in T is greater than 2, and that such a leaf can only occur when all other leaves in S are also leaves in T. Parallel results hold for k-minimal subtrees. Roughly speaking, the leaves of a k-maximal subtree tend to have degree 1 or 2 in T, while the leaves of a k-minimal subtree tend to have degree at least 3 in T. In the second part, this paper introduces the local density as a normalization oflocal means, for the sake of comparing subtrees of different orders. We show that the local density at subtree S is lower-bounded by 1/2 with equality if and only if S contains all the vertices of degree at least 3 in T. On the other hand, local density can be arbitrarily close to 1.

Given a tree T of order n , one can contract any edge and obtain a new tree T & lowast; of order n - 1. In 1983, Jamison made a conjecture that the mean subtree order, i.e., the average order of all subtrees, decreases at least 31 in contracting an edge of a tree. In 2023, Luo, Xu, Wagner and Wang proved the case when the edge to be contracted is a pendant edge. In this article, we prove that the conjecture is true in general. (c) 2024 The Author. Published by Elsevier Inc. This is an open access article under the CC BY license (http:// creativecommons.org/licenses/by/4.0/).