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

Basic Information

• Paper ID: 2510.10569
• Title: The Generalized Zagreb Index for Non-Plane and Plane Recursive Trees
• Authors: Qunqiang Feng (University of Science and Technology of China), Michael Fuchs (National Chengchi University), Tsan-Cheng Yu (Fu Jen Catholic University)
• Classification: math.PR (Probability), math.CO (Combinatorics)
• Publication Date: October 14, 2025 (arXiv preprint)
• Paper Link: https://arxiv.org/abs/2510.10569

Abstract

The Zagreb index is defined as the sum of squares of degrees of all vertices in a tree. Previous research has studied random non-plane recursive trees and tree classes approximating random plane recursive trees using martingale techniques. These techniques are difficult to apply directly to the generalized Zagreb index, which replaces the square with higher powers. This paper employs the moment transfer method to: (i) obtain first-order asymptotics of moments, (ii) prove limit laws for (appropriately normalized) generalized Zagreb indices of random non-plane and plane recursive trees. For the former, we prove that the limit law is normal for all higher-order powers; for the latter, we prove that the limit law is non-normal for cubic and quartic powers.

Research Background and Motivation

Problem Background

1. Importance of Zagreb Index: The Zagreb index is one of the most extensively studied topological indices in chemical graph theory, introduced by Gutman and Trinajstić in the 1970s. It is widely used for predicting physicochemical properties of compounds and has important applications in quantitative structure-property relationship (QSPR) and quantitative structure-activity relationship (QSAR) studies.
2. Generalized Zagreb Index: For a graph G=(V,E), the k-th order generalized Zagreb index is defined as: $Z_G^{(k)} = \sum_{v \in V} D_v^k = \sum_{uv \in E} (D_u^{k-1} + D_v^{k-1})$ where $D_v$ denotes the degree of vertex v. When k=2, this corresponds to the first Zagreb index; when k=3, it is called the forgotten topological index.
3. Limitations of Existing Methods:
   • Previous research on the first Zagreb index (k=2) primarily used martingale techniques and Stein's method
   • These techniques are difficult to extend to general k values
   • New methods are needed to handle the generalized Zagreb index
4. Research Objects:
   • Random non-plane recursive trees: child nodes are unordered
   • Random plane recursive trees: child nodes have left-right ordering

Core Contributions

1. Methodological Innovation: First application of the moment transfer method to the analysis of generalized Zagreb indices, overcoming limitations of traditional martingale techniques
2. Theoretical Results:
   • For random non-plane recursive trees: proved that for all k≥2, appropriately normalized generalized Zagreb indices converge to the standard normal distribution
   • For random plane recursive trees: proved convergence to non-normal distributions for k=3,4
3. Asymptotic Analysis: Obtained first-order asymptotic expressions for moments of all orders, providing a complete theoretical framework for understanding the statistical properties of these indices
4. Unified Framework: Provided a unified approach for handling different powers k, extending existing theory

Methodology Details

Task Definition

Study the asymptotic behavior of the generalized Zagreb index $Z_n^{(k)} = \sum_{v} D_v^k$ in random recursive trees, where:

• Input: Random recursive tree of size n
• Output: Limit distribution of the generalized Zagreb index
• Constraint: Appropriate normalization is required for the limit distribution to exist

Core Method: Moment Transfer Method

1. Distributional Recurrence Relations

For a random recursive tree of size n, the generalized Zagreb index satisfies the recurrence relation: $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$

where $I_n$ is the size of the root's leftmost subtree and $R_n$ is the degree of the root.

2. Moment Recurrence Equations

All central moments satisfy recurrence equations of the form: $a_n = \sum_{j=1}^{n-1} \pi_{n,j}(a_j + a_{n-j}) + b_n$

where $\pi_{n,j} = P(I_n = j)$ and $b_n$ is a function involving lower-order moments.

3. Asymptotic Transfer Results

Utilize established asymptotic transfer lemmas to derive asymptotics of $a_n$ from asymptotics of $b_n$:

Non-plane Recursive Trees (Lemmas 2.5-2.6):

• If $b_n = \hat{O}(n^α)$ with $0 ≤ α < 1$, then $a_n = μn + \hat{O}(n^α)$
• If $b_n \sim cn^α$ with $α > 1$, then $a_n \sim c(α+1)n^α/(α-1)$

Plane Recursive Trees (Lemmas 2.8-2.9):

• If $b_n \sim c\sqrt{n}$, then $a_n \sim cn\log n/\sqrt{π}$
• If $b_n \sim cn^α$ with $α > 1/2$, then $a_n \sim c\Gamma(α-1/2)n^{α+1/2}/\Gamma(α)$

Technical Innovations

1. Mixed Moment Analysis: Since recurrence relations involve the root degree $R_n$, simultaneous analysis of mixed moments of $Z_n^{(k)}$ and $R_n$ is required
2. Inductive Proof Strategy: Use lexicographic ordering on pairs $(r,s)$ for induction, where $r$ is the power of $Z_n$ and $s$ is the power of $R_n$
3. Differentiated Normalizations:
   • Non-plane trees: $(Z_n^{(k)} - μ_k n)/(σ_k\sqrt{n})$
   • Plane trees: $Z_n^{(k)}/n^{k/2}$

Experimental Setup

Theoretical Analysis Framework

This paper is primarily theoretical analysis without numerical experiments. The analysis framework includes:

1. Probabilistic Models:
   • Non-plane recursive trees: $I_n$ uniformly distributed on $\{1,...,n-1\}$
   • Plane recursive trees: $P(I_n = j) = \frac{2(n-j)C_jC_{n-j}}{nC_n}$
2. Moment Calculations: Compute asymptotic expressions for moments of various orders through recurrence relations
3. Limit Theorem Verification: Use the method of moments to prove convergence

Computational Examples

For the case k=2, the paper provides exact calculations:

• Non-plane trees: $μ_2 = 6$
• Plane trees: $E(Z_n^{(2)}) = 2n\log n + (4\log 2 + 2γ - 2)n + O(\sqrt{n})$

Experimental Results

Main Theoretical Results

Non-plane Recursive Trees (Theorem 3.1)

For all k≥2: $\frac{Z_n^{(k)} - μ_k n}{σ_k\sqrt{n}} \stackrel{d}{\rightarrow} N(0,1)$

where $μ_k, σ_k > 0$ are explicit constants.

Plane Recursive Trees (Theorem 4.1)

For k=3 or k=4: $\frac{Z_n^{(k)}}{n^{k/2}} \stackrel{d}{\rightarrow} Z^{(k)}$

where $Z^{(k)}$ is a non-normal random variable uniquely determined by its moment sequence.

Asymptotic Analysis Results

Asymptotic Behavior of Moments:

• Non-plane trees: $E(\bar{Z}_n^r) \sim g_r σ_k^r n^{r/2}$, where $g_r$ is the moment of the standard normal distribution
• Plane trees: $E(Z_n^r R_n^s) \sim g_{r,s} n^{(kr+s)/2}$

Convergence Conditions:

• For k=3,4, the moment sequence satisfies the Carleman condition, ensuring uniqueness of the distribution
• For k≥5, moment growth is too rapid for the moment method to apply

Key Findings

1. Phase Transition Phenomenon: Non-plane and plane trees exhibit completely different limiting behaviors
2. Power Effects: The value of k significantly affects the normalization scheme and type of limit distribution
3. Method Limitations: The moment transfer method is inapplicable for k≥5

Related Work

Main Research Directions

1. Zagreb Index Research:
   • Gutman & Trinajstić (1972): First introduction of Zagreb index
   • Widespread applications in QSPR/QSAR research
   • Research on extremal problems and bounds
2. Topological Indices on Random Trees:
   • Feng & Hu (2011, 2013): Study of first Zagreb index using martingale techniques
   • Zhang (2020): Related research on plane recursive trees
   • Research on Erdős-Rényi random graphs
3. Moment Transfer Method:
   • Neininger & Hwang (2002): Establishment of basic framework
   • Hwang (2006): Application to plane recursive trees
   • Chen & Fuchs (2011): Method improvements

Advantages of This Paper

1. Methodological Innovation: First application of moment transfer method to generalized Zagreb indices
2. Completeness of Results: Covers all feasible values of k
3. Theoretical Depth: Provides a complete asymptotic analysis framework

Conclusions and Discussion

Main Conclusions

1. Method Effectiveness: The moment transfer method successfully resolves generalized Zagreb index problems that martingale techniques cannot handle
2. Distribution Differences:
   • Non-plane recursive trees: All k≥2 converge to normal distribution
   • Plane recursive trees: k≥3 converge to non-normal distributions
3. Theoretical Completeness: Provides complete limit theory for k=3,4

Limitations

1. Method Constraints:
   • For plane recursive trees, the moment method fails for k≥5
   • k=2 requires special treatment
2. Technical Challenges:
   • Analysis of mixed moments is complex
   • Application of asymptotic transfer results requires precise error control
3. Scope of Applicability:
   • Applicable only to recursive tree models
   • Other random tree models require different transfer results

Future Directions

1. Method Extensions:
   • Seek new methods for handling k≥5 cases
   • Extend to other random tree models
2. Applied Research:
   • Practical applications in chemical graph theory
   • Relationships with other topological indices

In-Depth Evaluation

Strengths

1. Theoretical Contributions:
   • Resolves an important open problem
   • Provides new analytical tools and frameworks
   • Results have strong theoretical value
2. Methodological Innovation:
   • Skillful application of moment transfer method to new problems
   • Techniques for handling mixed moments have general applicability
3. Analytical Depth:
   • Complete asymptotic analysis
   • Rigorous mathematical proofs
   • Clear technical roadmap
4. Writing Quality:
   • Clear structure and rigorous logic
   • Complete technical details
   • Comprehensive review of related work

Weaknesses

1. Practical Limitations:
   • Pure theoretical research lacking numerical verification
   • Insufficient connection to practical applications
2. Method Limitations:
   • Cannot handle certain parameter ranges
   • Dependent on specific recursive tree models
3. Result Presentation:
   • Lacks concrete numerical examples
   • Properties of limit distributions not described in sufficient detail

Impact

1. Academic Contribution:
   • Provides new tools for interdisciplinary research between probability theory and combinatorics
   • May inspire research on other topological indices
2. Method Value:
   • New application of moment transfer method
   • Provides analytical framework for similar problems
3. Theoretical Significance:
   • Enriches random tree theory
   • Deepens understanding of asymptotic properties of topological indices

Applicable Scenarios

1. Theoretical Research: Probability theory, combinatorics, and graph theory research
2. Methodology: Provides reference for asymptotic analysis of other parameters
3. Application Background: Research on topological indices in chemical graph theory and network analysis

References

The paper cites 25 important references covering core works in Zagreb indices, random trees, moment transfer methods, and related fields, providing a solid theoretical foundation for the research.

Overall Assessment: This is a high-quality theoretical paper that successfully resolves the asymptotic analysis problem of generalized Zagreb indices on random recursive trees. The method is highly innovative, the results are complete and in-depth, and it has significant theoretical value for related fields. Although it has some limitations in practical applicability, its theoretical contributions and methodological significance make it an important advance in the field.