On the eccentric subtree number in trees (Q827611): Difference between revisions

This paper introduces and studies a novel concept with similar properties as the eccentricity, namely the eccentric subtree number. Let \(T\) be a tree. For vertices \(u\), \(v\), \(\eta_T(u,v)\) is the number of subtrees of \(T\) that contain both \(u\) and \(v\). The eccentric subtree number of a vertex \(v\) is defined as \[\eta_T^{ecc}(v) = \min_u \eta_T(v,u).\] An analogue of the diameter is defined as well: \[\eta^{\mathrm{diam}}(T) = \min_{u,v} \eta_T(u,v).\] Several elementary properties of eccentricity and diameter hold for these quantities as well. For example, the minimum of \(\eta_T(u,v)\) can only be attained by two leaves \(u\) and \(v\); if \(u\), \(v\) are such leaves, then one has, for arbitrary vertices \(w\), \[\eta^{ecc}(w) = \min(\eta(w,u),\eta(w,v)).\] The analogous statement is well known for the classical eccentricity and diameter. The maximum eccentric subtree number in a given tree \(T\) is either attained at a single vertex or two adjacent vertices -- this parallels the center of a tree, where the eccentricity is minimized. Lastly, several extremal problems are considered. The most basic theorem states that \[1 \leq \eta^{ecc}(v) \leq 2^{n-2}\] for a vertex \(v\) of a tree with \(n\) vertices. The paper concludes with a number of interesting open problems.