The Generalized Zagreb Index for Non-Plane and Plane Recursive Trees

基本信息

• 论文ID: 2510.10569
• 标题: The Generalized Zagreb Index for Non-Plane and Plane Recursive Trees
• 作者: Qunqiang Feng (University of Science and Technology of China), Michael Fuchs (National Chengchi University), Tsan-Cheng Yu (Fu Jen Catholic University)
• 分类: math.PR (Probability), math.CO (Combinatorics)
• 发表时间: October 14, 2025 (arXiv预印本)
• 论文链接: https://arxiv.org/abs/2510.10569

摘要

Zagreb指数定义为树中所有节点度数的平方和，之前的研究通过鞅技术对随机非平面递归树和接近随机平面递归树的树类进行了研究。这些技术难以直接应用于广义Zagreb指数，后者将平方替换为更高的幂次。本文采用矩传递方法来：(i) 获得矩的一阶渐近性，(ii) 证明随机非平面和平面递归树的（适当归一化的）广义Zagreb指数的极限定律；对于前者，我们证明了对于所有高阶幂次，极限定律都是正态的；对于后者，我们证明了对于三次和四次幂，其极限定律是非正态的。

研究背景与动机

问题背景

1. Zagreb指数的重要性：Zagreb指数是化学图论中最广泛研究的拓扑指数之一，由Gutman和Trinajstić在1970年代引入，广泛用于预测化合物的物理化学性质，在定量结构-性质关系(QSPR)和定量结构-活性关系(QSAR)研究中有重要应用。
2. 广义Zagreb指数：对于图G=(V,E)，k阶广义Zagreb指数定义为： $Z_G^{(k)} = \sum_{v \in V} D_v^k = \sum_{uv \in E} (D_u^{k-1} + D_v^{k-1})$ 其中$D_v$表示顶点v的度数。当k=2时对应第一Zagreb指数，k=3时称为遗忘拓扑指数。
3. 现有方法局限性：
   • 之前针对第一Zagreb指数(k=2)的研究主要使用鞅技术和Stein方法
   • 这些技术难以扩展到一般的k值
   • 需要新的方法来处理广义Zagreb指数
4. 研究对象：
   • 随机非平面递归树：子节点无序
   • 随机平面递归树：子节点有左右顺序

核心贡献

1. 方法创新：首次将矩传递方法应用于广义Zagreb指数的分析，克服了传统鞅技术的局限性
2. 理论结果：
   • 对于随机非平面递归树：证明了对所有k≥2，适当归一化的广义Zagreb指数收敛到标准正态分布
   • 对于随机平面递归树：证明了k=3,4时收敛到非正态分布
3. 渐近分析：获得了所有阶矩的一阶渐近表达式，为理解这些指数的统计性质提供了完整的理论框架
4. 统一框架：提供了处理不同幂次k的统一方法，扩展了现有理论

方法详解

任务定义

研究随机递归树中广义Zagreb指数$Z_n^{(k)} = \sum_{v} D_v^k$的渐近行为，其中：

• 输入：大小为n的随机递归树
• 输出：广义Zagreb指数的极限分布
• 约束：需要适当的归一化使极限分布存在

核心方法：矩传递方法

1. 分布递归关系

对于大小为n的随机递归树，广义Zagreb指数满足递归关系： $Z_n^{(k)} \stackrel{d}{=} Z_{I_n}^{(k)} + \tilde{Z}_{n-I_n}^{(k)} - R_{I_n}^k + (R_{I_n}+1)^k - \tilde{R}_{n-I_n}^k + (\tilde{R}_{n-I_n}+1)^k$

其中$I_n$是根的最左子树大小，$R_n$是根的度数。

2. 矩递归方程

所有中心矩满足形如以下的递归方程： $a_n = \sum_{j=1}^{n-1} \pi_{n,j}(a_j + a_{n-j}) + b_n$

其中$\pi_{n,j} = P(I_n = j)$，$b_n$是涉及低阶矩的函数。

3. 渐近传递结果

利用已建立的渐近传递引理来从$b_n$的渐近性推导$a_n$的渐近性：

非平面递归树（引理2.5-2.6）：

• 如果$b_n = \hat{O}(n^α)$且$0 ≤ α < 1$，则$a_n = μn + \hat{O}(n^α)$
• 如果$b_n \sim cn^α$且$α > 1$，则$a_n \sim c(α+1)n^α/(α-1)$

平面递归树（引理2.8-2.9）：

• 如果$b_n \sim c\sqrt{n}$，则$a_n \sim cn\log n/\sqrt{π}$
• 如果$b_n \sim cn^α$且$α > 1/2$，则$a_n \sim c\Gamma(α-1/2)n^{α+1/2}/\Γ(α)$

技术创新点

1. 混合矩分析：由于递归关系涉及根度数$R_n$，需要同时分析$Z_n^{(k)}$和$R_n$的混合矩
2. 归纳证明策略：使用字典序对$(r,s)$进行归纳，其中$r$是$Z_n$的幂次，$s$是$R_n$的幂次
3. 不同归一化：
   • 非平面树：$(Z_n^{(k)} - μ_k n)/(σ_k\sqrt{n})$
   • 平面树：$Z_n^{(k)}/n^{k/2}$

实验设置

理论分析框架

本文主要是理论分析，不涉及数值实验。分析框架包括：

1. 概率模型：
   • 非平面递归树：$I_n$均匀分布在$\{1,...,n-1\}$
   • 平面递归树：$P(I_n = j) = \frac{2(n-j)C_jC_{n-j}}{nC_n}$
2. 矩计算：通过递归关系计算各阶矩的渐近表达式
3. 极限定理验证：使用矩方法证明收敛性

计算实例

对于k=2的情况，文中给出了精确计算：

• 非平面树：$μ_2 = 6$
• 平面树：$E(Z_n^{(2)}) = 2n\log n + (4\log 2 + 2γ - 2)n + O(\sqrt{n})$

实验结果

主要理论结果

非平面递归树（定理3.1）

对于所有k≥2： $\frac{Z_n^{(k)} - μ_k n}{σ_k\sqrt{n}} \stackrel{d}{\rightarrow} N(0,1)$

其中$μ_k, σ_k > 0$是明确的常数。

平面递归树（定理4.1）

对于k=3或k=4： $\frac{Z_n^{(k)}}{n^{k/2}} \stackrel{d}{\rightarrow} Z^{(k)}$

其中$Z^{(k)}$是由矩序列唯一确定的非正态随机变量。

渐近分析结果

矩的渐近行为：

• 非平面树：$E(\bar{Z}_n^r) \sim g_r σ_k^r n^{r/2}$，其中$g_r$是标准正态分布的矩
• 平面树：$E(Z_n^r R_n^s) \sim g_{r,s} n^{(kr+s)/2}$

收敛条件：

• k=3,4时矩序列满足Carleman条件，保证分布唯一性
• k≥5时矩增长过快，矩方法不适用

关键发现

1. 相变现象：非平面树和平面树表现出完全不同的极限行为
2. 幂次效应：k的值显著影响归一化方式和极限分布类型
3. 方法局限性：矩传递方法对k≥5的情况不适用

相关工作

主要研究方向

1. Zagreb指数研究：
   • Gutman & Trinajstić (1972)：首次引入Zagreb指数
   • 广泛应用于QSPR/QSAR研究
   • 极值问题和界的研究
2. 随机树上的拓扑指数：
   • Feng & Hu (2011, 2013)：使用鞅技术研究第一Zagreb指数
   • Zhang (2020)：平面递归树的相关研究
   • Erdős-Rényi随机图上的研究
3. 矩传递方法：
   • Neininger & Hwang (2002)：建立基本框架
   • Hwang (2006)：平面递归树的应用
   • Chen & Fuchs (2011)：方法的改进

本文优势

1. 方法创新：首次将矩传递方法应用于广义Zagreb指数
2. 结果完整性：覆盖了所有可行的k值
3. 理论深度：提供了完整的渐近分析框架

结论与讨论

主要结论

1. 方法有效性：矩传递方法成功解决了鞅技术无法处理的广义Zagreb指数问题
2. 分布差异：
   • 非平面递归树：所有k≥2都收敛到正态分布
   • 平面递归树：k≥3收敛到非正态分布
3. 理论完备性：为k=3,4提供了完整的极限理论

局限性

1. 方法限制：
   • 对平面递归树，k≥5时矩方法失效
   • k=2需要特殊处理
2. 技术挑战：
   • 混合矩的分析复杂
   • 渐近传递结果的应用需要精确的误差控制
3. 适用范围：
   • 仅适用于递归树模型
   • 其他随机树模型需要不同的传递结果

未来方向

1. 方法扩展：
   • 寻找处理k≥5情况的新方法
   • 扩展到其他随机树模型
2. 应用研究：
   • 在化学图论中的实际应用
   • 与其他拓扑指数的关系

深度评价

优点

1. 理论贡献：
   • 解决了一个重要的开放问题
   • 提供了新的分析工具和框架
   • 结果具有较强的理论价值
2. 方法创新：
   • 巧妙地将矩传递方法应用于新问题
   • 处理混合矩的技术具有一般性
3. 分析深度：
   • 完整的渐近分析
   • 严格的数学证明
   • 清晰的技术路线
4. 写作质量：
   • 结构清晰，逻辑严密
   • 技术细节完整
   • 相关工作梳理全面

不足

1. 实用性限制：
   • 纯理论研究，缺乏数值验证
   • 与实际应用的联系不够紧密
2. 方法局限：
   • 对某些参数范围无法处理
   • 依赖于特定的递归树模型
3. 结果展示：
   • 缺乏具体的数值例子
   • 极限分布的性质描述不够详细

影响力

1. 学术贡献：
   • 为概率论和组合数学的交叉研究提供新工具
   • 可能启发其他拓扑指数的研究
2. 方法价值：
   • 矩传递方法的新应用
   • 为类似问题提供分析框架
3. 理论意义：
   • 丰富了随机树理论
   • 深化了对拓扑指数渐近性质的理解

适用场景

1. 理论研究：概率论、组合数学、图论研究
2. 方法学：为其他参数的渐近分析提供参考
3. 应用背景：化学图论、网络分析中的拓扑指数研究

参考文献

论文引用了25篇重要文献，涵盖了Zagreb指数、随机树、矩传递方法等相关领域的核心工作，为研究提供了坚实的理论基础。

总评：这是一篇高质量的理论论文，成功解决了广义Zagreb指数在随机递归树上的渐近分析问题。方法创新性强，结果完整深入，对相关领域具有重要的理论价值。尽管在实用性方面有所不足，但其理论贡献和方法学意义使其成为该领域的重要进展。