Extrema of local mean and local density in a tree

arXiv2306.13422MaRDI QIDQ6441237FDOQ6441237

Publication date: 23 June 2023

Abstract: Given a tree T, one can define the local mean at some subtree S to be the average order of subtrees containing S. It is natural to ask which subtree of order k achieves the maximal/minimal local mean among all the subtrees of the same order and what properties it has. We call such subtrees k-maximal subtrees. Wagner and Wang showed in 2016 that a 1- maximal subtree is a vertex of degree 1 or 2. This paper shows that for any integer k = 1, . . . , |T| , a k-maximal subtree has at most one leaf whose degree is greater than 2 and at least one leaf whose degree is at most 2. Furthermore, we show that a k-maximal subtree has a leaf of degree greater than 2 only when all its other leaves are leaves in T as well. 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, and shows that the local density at subtree S is lower-bounded by 1/2 with equality if and only if S contains the core of T. On the other hand, local density can be arbitrarily close to 1.

This page was built for publication: Extrema of local mean and local density in a tree

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6441237)