On Extremal Family Trees $(\mathcal{T}_n)_{n\geqslant 3}$ Beyond Caterpillars and Greedy Constructions

技术摘要：超越毛虫树与贪婪构造的极值树族研究

问题陈述
本文研究了在所有具有 $n \geq 3$ 个顶点的树族 $\mathcal{T}_n$ 中，Sigma 指数（$\sigma$）的极值性质。Sigma 指数是一个衡量图不规则性的二次测度，定义为 $\sigma(G) = \sum_{uv \in E(G)} (d_G(u) - d_G(v))^2$。本研究旨在解决的核心挑战是建立 $\sigma$ 的精确界限，并理解哪些树的结构类实现了这些界限。具体而言，作者将 $\sigma$ 在所有树上的全局最小值与在受限子类（即毛虫树和贪婪树——通过连接顶点以在局部最小化度差异来构造的树）中取得的最小值进行了比较。此外，本研究还试图确定是否存在既不是毛虫树也不是贪婪树的树，其 $\sigma$ 值严格介于全局最小值与毛虫树最小值之间。

方法论
作者结合了结构图论与组合优化方法：

1. 定义与预备知识： 文中建立了毛虫树（移除叶节点后剩余部分为路径的树）和贪婪树（通过迭代地将新顶点连接到当前度数最小且尚未达到目标度数的顶点来构造的树）的定义。
2. 变换论证： 为了证明极值性质，作者利用了边交换操作。他们证明了对于任何非贪婪树，存在特定的边交换（通过重新连接顶点以遵循度数排序）可以严格降低 Sigma 指数，从而证明了贪婪树在给定度序列下使 $\sigma$ 最小。
3. 分类讨论与归纳法： 作者对由“问题 1”和“问题 2”定义的特定树结构进行了分析。这些问题定义了具有中心脊柱以及具有特定度约束的多层悬挂顶点的树（例如，第一层悬挂顶点度数为 $1+r$，第二层为 $1+s$，依此类推）。
4. 公式推导： 通过根据树的层级（脊柱到第一层、第一层到第二层等）对边进行划分，作者推导出了这些结构化树族的 $\sigma(T)$ 的精确代数公式。他们还通过分析度序列的排序来确定毛虫树的最大和最小 $\sigma$ 值。

主要贡献与结果

• 贪婪树的极值性质： 本文证明了对于任何图形度序列 $D$，贪婪树 $T_D$ 在实现 $D$ 的所有树中使 Sigma 指数最小。
• 毛虫树的局限性： 作者证明了毛虫树并未在整个树族 $\mathcal{T}_n$ 中实现 $\sigma$ 的全局最小值。
• 中间极值树的存在性： 一个重要的发现是，本文证明了存在既不是毛虫树也不是贪婪树，但其 $\sigma$ 值严格介于全局最小值与毛虫树最小值之间的树。这确立了一个将全局最小值与毛虫树最小值分隔开的非空开区间。
• 结构化树的精确公式：
  • 引理 3.2 & 3.3： 本文推导了在不同度数条件（线性与平方度增长）下，具有三层悬挂顶点的树的 Sigma 指数的显式公式。
  • 定理 3.6： 提供了一个针对具有 $n$ 个脊柱顶点和 $k$ 层悬挂顶点的树的通用公式，该公式考虑了分支因子乘积与层间度数平方差。
  • 命题 3.3： 提供了毛虫树 $C(n, m)$ 的 Sigma 指数的精确公式，并区分了 $n=2$ 和 $n>2$ 的情况。
• 界限： 本文给出了涉及平均度数和平方度数差之和的毛虫树 $\sigma$ 的上界（定理 3.7）。

意义
本文声称为非毛虫、非贪婪树在最小化图不变量中的作用提供了新的见解。通过证明 Sigma 指数的全局最小值并不局限于广泛研究的毛虫树或贪婪树类，这项工作强调了在使用这些常见类别处理极值问题时的结构性局限。所推导的精确公式和界限提供了一个统一的分析框架，用于比较树的线性与二次不规则性测度。作者将这些结果定位为研究拓扑指数（特别是针对结构化树族）的基础基石，为经过固定规模示例和一般序列验证的精确公式提供了支撑。