2025-11-23T10:19:17.258700

The generalized Zagreb index for non-plane and plane recursive trees

Feng, Fuchs, Yu
The Zagreb index, which is defined as the sum of squares of degrees of the nodes of a tree, was studied in previous works by martingale techniques for random non-plane recursive trees and classes of random trees which are close to random plane recursive trees. These techniques are not easily amended to the generalized Zagreb index, which is defined similar but with squares replaced by higher powers. In this paper, we use the moment transfer approach to (i) obtain the first-order asymptotics of moments and to (ii) prove limit laws for the (suitable normalized) generalized Zagreb index for random non-plane and plane recursive trees; for the former, we show that for all higher powers the limit law is normal, for the latter, we show for cubes and fourth powers that its a non-normal law.
academic

Der verallgemeinerte Zagreb-Index für nicht-ebene und ebene rekursive Bäume

Grundlegende Informationen

  • Papier-ID: 2510.10569
  • Titel: The Generalized Zagreb Index for Non-Plane and Plane Recursive Trees
  • Autoren: Qunqiang Feng (University of Science and Technology of China), Michael Fuchs (National Chengchi University), Tsan-Cheng Yu (Fu Jen Catholic University)
  • Klassifizierung: math.PR (Wahrscheinlichkeitstheorie), math.CO (Kombinatorik)
  • Veröffentlichungsdatum: 14. Oktober 2025 (arXiv-Preprint)
  • Papier-Link: https://arxiv.org/abs/2510.10569

Zusammenfassung

Der Zagreb-Index ist definiert als die Summe der Quadrate der Grade aller Knoten in einem Baum. Frühere Forschungen untersuchten zufällige nicht-ebene rekursive Bäume und Baumklassen nahe zufälligen ebenen rekursiven Bäumen mittels Martingal-Techniken. Diese Techniken lassen sich nicht direkt auf den verallgemeinerten Zagreb-Index anwenden, der die Quadrate durch höhere Potenzen ersetzt. In diesem Artikel wird eine Momentenübertragungsmethode verwendet, um: (i) asymptotische Ausdrücke erster Ordnung für Momente zu erhalten, (ii) Grenzgesetze für (angemessen normalisierte) verallgemeinerte Zagreb-Indizes zufälliger nicht-ebener und ebener rekursiver Bäume zu beweisen. Für erstere zeigen wir, dass die Grenzgesetze für alle höheren Potenzen normal sind; für letztere zeigen wir, dass die Grenzgesetze für kubische und quartische Potenzen nicht-normal sind.

Forschungshintergrund und Motivation

Problemhintergrund

  1. Bedeutung des Zagreb-Index: Der Zagreb-Index ist einer der am weitesten untersuchten topologischen Indizes in der chemischen Graphentheorie. Er wurde von Gutman und Trinajstić in den 1970er Jahren eingeführt und wird häufig zur Vorhersage physikalisch-chemischer Eigenschaften von Verbindungen verwendet. Er findet wichtige Anwendungen in der quantitativen Struktur-Eigenschafts-Beziehung (QSPR) und der quantitativen Struktur-Aktivitäts-Beziehung (QSAR).
  2. Verallgemeinerter Zagreb-Index: Für einen Graphen G=(V,E) ist der verallgemeinerte Zagreb-Index k-ter Ordnung definiert als: ZG(k)=∑v∈VDvk=∑uv∈E(Duk−1+Dvk−1)Z_G^{(k)} = \sum_{v \in V} D_v^k = \sum_{uv \in E} (D_u^{k-1} + D_v^{k-1}) wobei DvD_v den Grad des Knotens v bezeichnet. Für k=2 entspricht dies dem ersten Zagreb-Index, für k=3 wird es als vergessener topologischer Index bezeichnet.
  3. Einschränkungen bestehender Methoden:
    • Frühere Forschungen zum ersten Zagreb-Index (k=2) verwendeten hauptsächlich Martingal-Techniken und die Stein-Methode
    • Diese Techniken lassen sich nicht leicht auf allgemeine k-Werte erweitern
    • Neue Methoden sind erforderlich, um den verallgemeinerten Zagreb-Index zu behandeln
  4. Forschungsobjekte:
    • Zufällige nicht-ebene rekursive Bäume: Kindknoten sind ungeordnet
    • Zufällige ebene rekursive Bäume: Kindknoten haben eine Links-Rechts-Ordnung

Kernbeiträge

  1. Methodische Innovation: Erstmalige Anwendung der Momentenübertragungsmethode auf die Analyse des verallgemeinerten Zagreb-Index, was die Einschränkungen traditioneller Martingal-Techniken überwindet
  2. Theoretische Ergebnisse:
    • Für zufällige nicht-ebene rekursive Bäume: Beweis, dass der angemessen normalisierte verallgemeinerte Zagreb-Index für alle k≥2 gegen die Standardnormalverteilung konvergiert
    • Für zufällige ebene rekursive Bäume: Beweis, dass für k=3,4 gegen eine nicht-normale Verteilung konvergiert
  3. Asymptotische Analyse: Erhalten von asymptotischen Ausdrücken erster Ordnung für alle Momente, was einen vollständigen theoretischen Rahmen zum Verständnis der statistischen Eigenschaften dieser Indizes bietet
  4. Einheitlicher Rahmen: Bereitstellung einer einheitlichen Methode zur Behandlung verschiedener Potenzen k, Erweiterung der bestehenden Theorie

Methodische Details

Aufgabendefinition

Untersuchung des asymptotischen Verhaltens des verallgemeinerten Zagreb-Index Zn(k)=∑vDvkZ_n^{(k)} = \sum_{v} D_v^k in zufälligen rekursiven Bäumen, wobei:

  • Eingabe: Zufälliger rekursiver Baum der Größe n
  • Ausgabe: Grenzverteilung des verallgemeinerten Zagreb-Index
  • Einschränkungen: Angemessene Normalisierung erforderlich, damit die Grenzverteilung existiert

Kernmethode: Momentenübertragungsmethode

1. Verteilungsrekursionsrelation

Für einen zufälligen rekursiven Baum der Größe n erfüllt der verallgemeinerte Zagreb-Index die Rekursionsrelation: Zn(k)=dZIn(k)+Z~n−In(k)−RInk+(RIn+1)k−R~n−Ink+(R~n−In+1)kZ_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

wobei InI_n die Größe des linkesten Teilbaums der Wurzel ist und RnR_n der Grad der Wurzel ist.

2. Momentenrekursionsgleichungen

Alle zentralen Momente erfüllen Rekursionsgleichungen der folgenden Form: an=∑j=1n−1πn,j(aj+an−j)+bna_n = \sum_{j=1}^{n-1} \pi_{n,j}(a_j + a_{n-j}) + b_n

wobei πn,j=P(In=j)\pi_{n,j} = P(I_n = j) und bnb_n eine Funktion ist, die niedrigere Momente beinhaltet.

3. Asymptotische Übertragungsergebnisse

Verwendung etablierter asymptotischer Übertragungslemmata, um von der Asymptotik von bnb_n auf die Asymptotik von ana_n zu schließen:

Nicht-ebene rekursive Bäume (Lemma 2.5-2.6):

  • Wenn bn=O^(nα)b_n = \hat{O}(n^α) und 0≤α<10 ≤ α < 1, dann an=μn+O^(nα)a_n = μn + \hat{O}(n^α)
  • Wenn bn∼cnαb_n \sim cn^α und α>1α > 1, dann an∼c(α+1)nα/(α−1)a_n \sim c(α+1)n^α/(α-1)

Ebene rekursive Bäume (Lemma 2.8-2.9):

  • Wenn bn∼cnb_n \sim c\sqrt{n}, dann an∼cnlog⁡n/πa_n \sim cn\log n/\sqrt{π}
  • Wenn bn∼cnαb_n \sim cn^α und α>1/2α > 1/2, dann an∼cΓ(α−1/2)nα+1/2/Γ(α)a_n \sim c\Gamma(α-1/2)n^{α+1/2}/\Gamma(α)

Technische Innovationspunkte

  1. Gemischte Momentenanalyse: Da die Rekursionsrelation den Wurzelgrad RnR_n beinhaltet, ist eine gleichzeitige Analyse gemischter Momente von Zn(k)Z_n^{(k)} und RnR_n erforderlich
  2. Induktive Beweisstrategien: Verwendung lexikographischer Ordnung auf Paaren (r,s)(r,s), wobei rr die Potenz von ZnZ_n und ss die Potenz von RnR_n ist
  3. Unterschiedliche Normalisierungen:
    • Nicht-ebene Bäume: (Zn(k)−μkn)/(σkn)(Z_n^{(k)} - μ_k n)/(σ_k\sqrt{n})
    • Ebene Bäume: Zn(k)/nk/2Z_n^{(k)}/n^{k/2}

Experimentelle Einrichtung

Theoretischer Analysrahmen

Dieser Artikel ist hauptsächlich eine theoretische Analyse und beinhaltet keine numerischen Experimente. Der Analysrahmen umfasst:

  1. Wahrscheinlichkeitsmodelle:
    • Nicht-ebene rekursive Bäume: InI_n gleichmäßig verteilt auf {1,...,n−1}\{1,...,n-1\}
    • Ebene rekursive Bäume: P(In=j)=2(n−j)CjCn−jnCnP(I_n = j) = \frac{2(n-j)C_jC_{n-j}}{nC_n}
  2. Momentenberechnung: Berechnung asymptotischer Ausdrücke für Momente verschiedener Ordnungen durch Rekursionsrelationen
  3. Grenzwertsatzverifikation: Verwendung der Momentenmethode zum Beweis der Konvergenz

Berechnungsbeispiele

Für den Fall k=2 werden im Artikel genaue Berechnungen angegeben:

  • Nicht-ebene Bäume: μ2=6μ_2 = 6
  • Ebene Bäume: E(Zn(2))=2nlog⁡n+(4log⁡2+2γ−2)n+O(n)E(Z_n^{(2)}) = 2n\log n + (4\log 2 + 2γ - 2)n + O(\sqrt{n})

Experimentelle Ergebnisse

Haupttheoretische Ergebnisse

Nicht-ebene rekursive Bäume (Satz 3.1)

Für alle k≥2: Zn(k)−μknσkn→dN(0,1)\frac{Z_n^{(k)} - μ_k n}{σ_k\sqrt{n}} \stackrel{d}{\rightarrow} N(0,1)

wobei μk,σk>0μ_k, σ_k > 0 explizite Konstanten sind.

Ebene rekursive Bäume (Satz 4.1)

Für k=3 oder k=4: Zn(k)nk/2→dZ(k)\frac{Z_n^{(k)}}{n^{k/2}} \stackrel{d}{\rightarrow} Z^{(k)}

wobei Z(k)Z^{(k)} eine nicht-normale Zufallsvariable ist, die eindeutig durch ihre Momentenfolge bestimmt wird.

Asymptotische Analyseergebnisse

Asymptotisches Verhalten von Momenten:

  • Nicht-ebene Bäume: E(Zˉnr)∼grσkrnr/2E(\bar{Z}_n^r) \sim g_r σ_k^r n^{r/2}, wobei grg_r das r-te Moment der Standardnormalverteilung ist
  • Ebene Bäume: E(ZnrRns)∼gr,sn(kr+s)/2E(Z_n^r R_n^s) \sim g_{r,s} n^{(kr+s)/2}

Konvergenzbedingungen:

  • Für k=3,4 erfüllt die Momentenfolge die Carleman-Bedingung, was die Eindeutigkeit der Verteilung garantiert
  • Für k≥5 wächst das Momentenwachstum zu schnell, die Momentenmethode ist nicht anwendbar

Wichtigste Erkenntnisse

  1. Phasenübergänge: Nicht-ebene und ebene Bäume zeigen völlig unterschiedliche Grenzverhalten
  2. Potenzeffekte: Der Wert von k beeinflusst erheblich die Normalisierungsweise und den Typ der Grenzverteilung
  3. Methodische Einschränkungen: Die Momentenübertragungsmethode ist für k≥5 nicht anwendbar

Verwandte Arbeiten

Hauptforschungsrichtungen

  1. Zagreb-Index-Forschung:
    • Gutman & Trinajstić (1972): Erstmalige Einführung des Zagreb-Index
    • Weit verbreitete Anwendung in QSPR/QSAR-Forschung
    • Forschung zu Extremalproblemen und Schranken
  2. Topologische Indizes auf zufälligen Bäumen:
    • Feng & Hu (2011, 2013): Verwendung von Martingal-Techniken zur Untersuchung des ersten Zagreb-Index
    • Zhang (2020): Verwandte Forschung zu ebenen rekursiven Bäumen
    • Forschung auf Erdős-Rényi-Zufallsgraphen
  3. Momentenübertragungsmethode:
    • Neininger & Hwang (2002): Etablierung des grundlegenden Rahmens
    • Hwang (2006): Anwendung auf ebene rekursive Bäume
    • Chen & Fuchs (2011): Verbesserungen der Methode

Vorteile dieses Artikels

  1. Methodische Innovation: Erstmalige Anwendung der Momentenübertragungsmethode auf den verallgemeinerten Zagreb-Index
  2. Vollständigkeit der Ergebnisse: Abdeckung aller praktikablen k-Werte
  3. Theoretische Tiefe: Bereitstellung eines vollständigen asymptotischen Analysrahmens

Schlussfolgerungen und Diskussion

Hauptschlussfolgerungen

  1. Methodische Wirksamkeit: Die Momentenübertragungsmethode löst erfolgreich Probleme des verallgemeinerten Zagreb-Index, die Martingal-Techniken nicht bewältigen können
  2. Verteilungsunterschiede:
    • Nicht-ebene rekursive Bäume: Alle k≥2 konvergieren gegen die Normalverteilung
    • Ebene rekursive Bäume: k≥3 konvergiert gegen nicht-normale Verteilungen
  3. Theoretische Vollständigkeit: Bereitstellung einer vollständigen Grenztheorie für k=3,4

Einschränkungen

  1. Methodische Beschränkungen:
    • Für ebene rekursive Bäume versagt die Momentenmethode bei k≥5
    • k=2 erfordert spezielle Behandlung
  2. Technische Herausforderungen:
    • Analyse gemischter Momente ist komplex
    • Die Anwendung asymptotischer Übertragungsergebnisse erfordert präzise Fehlerkontrollen
  3. Anwendungsbereich:
    • Nur auf rekursive Baummodelle anwendbar
    • Andere Zufallsbaummodelle erfordern unterschiedliche Übertragungsergebnisse

Zukünftige Richtungen

  1. Methodische Erweiterungen:
    • Suche nach neuen Methoden zur Behandlung von k≥5
    • Erweiterung auf andere Zufallsbaummodelle
  2. Anwendungsforschung:
    • Praktische Anwendungen in der chemischen Graphentheorie
    • Beziehungen zu anderen topologischen Indizes

Tiefgreifende Bewertung

Stärken

  1. Theoretische Beiträge:
    • Lösung eines wichtigen offenen Problems
    • Bereitstellung neuer Analysewerkzeuge und Rahmen
    • Ergebnisse haben hohen theoretischen Wert
  2. Methodische Innovation:
    • Geschickte Anwendung der Momentenübertragungsmethode auf neue Probleme
    • Techniken zur Behandlung gemischter Momente haben allgemeine Gültigkeit
  3. Analystiefe:
    • Vollständige asymptotische Analyse
    • Strenge mathematische Beweise
    • Klare technische Roadmap
  4. Schreibqualität:
    • Klare Struktur, strenge Logik
    • Vollständige technische Details
    • Umfassende Aufarbeitung verwandter Arbeiten

Schwächen

  1. Praktische Einschränkungen:
    • Rein theoretische Forschung, fehlende numerische Verifikation
    • Unzureichende Verbindung zu praktischen Anwendungen
  2. Methodische Einschränkungen:
    • Kann bestimmte Parameterbereiche nicht behandeln
    • Abhängigkeit von spezifischen rekursiven Baummodellen
  3. Ergebnispräsentation:
    • Mangel an konkreten numerischen Beispielen
    • Unzureichend detaillierte Beschreibung der Eigenschaften von Grenzverteilungen

Einfluss

  1. Akademische Beiträge:
    • Bereitstellung neuer Werkzeuge für interdisziplinäre Forschung zwischen Wahrscheinlichkeitstheorie und Kombinatorik
    • Kann Forschung zu anderen topologischen Indizes inspirieren
  2. Methodischer Wert:
    • Neue Anwendung der Momentenübertragungsmethode
    • Analysrahmen für ähnliche Probleme
  3. Theoretische Bedeutung:
    • Bereicherung der Theorie zufälliger Bäume
    • Vertiefung des Verständnisses asymptotischer Eigenschaften topologischer Indizes

Anwendungsszenarien

  1. Theoretische Forschung: Wahrscheinlichkeitstheorie, Kombinatorik, Graphentheorie
  2. Methodologie: Referenz für asymptotische Analyse anderer Parameter
  3. Anwendungshintergrund: Forschung zu topologischen Indizes in chemischer Graphentheorie und Netzwerkanalyse

Literaturverzeichnis

Der Artikel zitiert 25 wichtige Arbeiten, die Kernarbeiten in verwandten Bereichen wie Zagreb-Index, zufällige Bäume und Momentenübertragungsmethode abdecken und eine solide theoretische Grundlage für die Forschung bieten.

Gesamtbewertung: Dies ist ein hochqualitatives theoretisches Papier, das das asymptotische Analyseproblem des verallgemeinerten Zagreb-Index auf zufälligen rekursiven Bäumen erfolgreich löst. Die Methode ist innovativ, die Ergebnisse sind vollständig und tiefgreifend, und sie hat wichtigen theoretischen Wert für verwandte Bereiche. Obwohl sie in praktischer Hinsicht einige Einschränkungen hat, machen ihr theoretischer Beitrag und methodischer Wert sie zu einem wichtigen Fortschritt in diesem Bereich.