Extrema of Local Mean and Local Density in a Tree

Abstract

Given a tree $T$ and a subtree $S$ of $T,$ one can define the local mean at $S,$ $\mu_{T}\left(S\right),$ to be the average order of the subtrees of $T$ containing $S.$ In 1983, Jamison showed that $\mu_{T}\left(S\right)<\mu_{T}(S^{'})$ if $S\subset 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 2016 that 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\geq2,$ 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 of local 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.