2025-11-10T02:45:05.969614

On a Conjecture Concerning the Complementary Second Zagreb Index

Saber, Alraqad, Ali et al.
The complementary second Zagreb index of a graph $G$ is defined as $cM_2(G)=\sum_{uv\in E(G)}|(d_u(G))^2-(d_v(G))^2|$, where $d_u(G)$ denotes the degree of a vertex $u$ in $G$ and $E(G)$ represents the edge set of $G$. Let $G^*$ be a graph having the maximum value of $cM_2$ among all connected graphs of order $n$. Furtula and Oz [MATCH Commun. Math. Comput. Chem. 93 (2025) 247--263] conjectured that $G^*$ is the join $K_k+\overline{K}_{n-k}$ of the complete graph $K_k$ of order $k$ and the complement $\overline{K}_{n-k}$ of the complete graph $K_{n-k}$ such that the inequality $k<\lceil n/2 \rceil$ holds. We prove that (i) the maximum degree of $G^*$ is $n-1$ and (ii) no two vertices of minimum degree in $G^*$ are adjacent; both of these results support the aforementioned conjecture. We also prove that the number of vertices of maximum degree in $G^*$, say $k$, is at most $-\frac{2}{3}n+\frac{3}{2}+\frac{1}{6}\sqrt{52n^2-132n+81}$, which implies that $k<5352n/10000$. Furthermore, we establish results that support the conjecture under consideration for certain bidegreed and tridegreed graphs. In the aforesaid paper, it was also mentioned that determining the $k$ as a function of the $n$ is far from being an easy task; we obtain the values of $k$ for $5\le n\le 149$ in the case of certain bidegreed graphs by using computer software and found that the resulting sequence of the values of $k$ does not exist in "The On-Line Encyclopedia of Integer Sequences" (an online database of integer sequences).
academic

Über eine Vermutung zum komplementären zweiten Zagreb-Index

Grundinformationen

  • Paper-ID: 2501.01295
  • Titel: On a Conjecture Concerning the Complementary Second Zagreb Index
  • Autoren: Hicham Saber, Tariq Alraqad, Akbar Ali, Abdulaziz M. Alanazi, Zahid Raza
  • Klassifikation: math.CO (Kombinatorik)
  • Einreichungsdatum: 2. Januar 2025 bei arXiv
  • Paper-Link: https://arxiv.org/abs/2501.01295

Zusammenfassung

Diese Arbeit untersucht Extremwertprobleme des komplementären zweiten Zagreb-Index von Graphen. Der komplementäre zweite Zagreb-Index ist definiert als cM2(G)=∑uv∈E(G)∣(du(G))2−(dv(G))2∣cM_2(G)=\sum_{uv\in E(G)}|(d_u(G))^2-(d_v(G))^2|, wobei du(G)d_u(G) den Grad des Knotens uu im Graphen GG bezeichnet. Die Autoren führen eine tiefgehende Untersuchung einer von Furtula und Oz aufgestellten Vermutung durch, die besagt, dass unter allen zusammenhängenden Graphen der Ordnung nn der Graph G∗G^*, der cM2cM_2 maximiert, die Verbindung des vollständigen Graphen KkK_k mit seinem Komplement K‾n−k\overline{K}_{n-k} ist, wobei k<⌈n/2⌉k<\lceil n/2 \rceil gilt.

Forschungshintergrund und Motivation

Problemhintergrund

  1. Bedeutung molekularer Deskriptoren: Molekulare Deskriptoren sind grundlegende Werkzeuge für die virtuelle Durchsuchung von Molekülbibliotheken und die Vorhersage physikalisch-chemischer Eigenschaften von Molekülen. In der chemischen Graphentheorie werden durch Molekülgraphen definierte Deskriptoren als topologische Indizes bezeichnet.
  2. Gradbasierte topologische Indizes: Topologische Indizes, die auf Knotengraden basieren, finden in der chemischen Graphentheorie breite Anwendung. Der komplementäre zweite Zagreb-Index (CSZ-Index) ist ein kürzlich eingeführter neuer gradbasisierter topologischer Index.
  3. Extremwertprobleme: Die Bestimmung von Graphstrukturen, die einen bestimmten topologischen Index unter gegebenen Nebenbedingungen extremalisieren, ist ein wichtiges Problem in der Graphentheorie mit theoretischem und praktischem Wert.

Forschungsmotivation

  1. Theoretische Vervollständigung: Furtula und Oz stellten 2025 eine Vermutung über die Extremalgraphstrukturen des CSZ-Index auf, denen jedoch strenge mathematische Beweise fehlen.
  2. Rechnerische Komplexität: Die Bestimmung der Anzahl kk der Knoten mit maximalem Grad als Funktion von nn wird als „alles andere als trivial" angesehen und erfordert neue theoretische Werkzeuge und Rechenmethoden.
  3. Anwendungswert: Das Verständnis der Extremaleigenschaften des CSZ-Index ist für die chemische Graphentheorie und Moleküldesign von großer Bedeutung.

Kernbeiträge

Die Hauptbeiträge dieser Arbeit umfassen:

  1. Beweis der Maximalgradeigenschaft von Extremalgraphen: Es wird bewiesen, dass der zusammenhängende Graph G∗G^* der Ordnung nn, der cM2cM_2 maximiert, einen maximalen Grad von n−1n-1 hat.
  2. Aufdeckung der Nachbarschaftseigenschaft von Knoten mit minimalem Grad: Es wird bewiesen, dass je zwei Knoten mit minimalem Grad in G∗G^* nicht benachbart sind.
  3. Etablierung einer Obergrenze für die Anzahl der Knoten mit maximalem Grad: Es wird bewiesen, dass die Anzahl kk der Knoten mit maximalem Grad in G∗G^* erfüllt: k≤−23n+32+1652n2−132n+81<5352n10000k \leq -\frac{2}{3}n+\frac{3}{2}+\frac{1}{6}\sqrt{52n^2-132n+81} < \frac{5352n}{10000}
  4. Verifikation der Vermutung für spezielle Graphklassen: Die Furtula-Oz-Vermutung wird für Graphen mit zwei und drei verschiedenen Graden vollständig bewiesen.
  5. Bereitstellung von Rechendaten: Durch Computersoftware werden die kk-Werte für den Fall von Graphen mit zwei verschiedenen Graden im Bereich 5≤n≤1495 \leq n \leq 149 berechnet. Die resultierende Sequenz existiert nicht in der Online-Enzyklopädie der Ganzzahlfolgen.

Methodische Darlegung

Aufgabendefinition

Untersuchung der Struktureigenschaften von Graphen, die den komplementären zweiten Zagreb-Index cM2(G)=∑uv∈E(G)∣(du(G))2−(dv(G))2∣cM_2(G) = \sum_{uv\in E(G)}|(d_u(G))^2-(d_v(G))^2| unter allen zusammenhängenden Graphen der Ordnung nn maximieren.

Kernsätze und Beweismethoden

Satz 1 (Proposition 2): Maximalgradeigenschaft

Aussage: Wenn ein Graph GG unter allen zusammenhängenden Graphen der Ordnung nn den maximalen cM2cM_2-Wert hat und n≥4n \geq 4 ist, dann ist der maximale Grad von GG gleich n−1n-1.

Beweisidee:

  1. Annahme: maximaler Grad Δ<n−1\Delta < n-1; Auswahl eines Knotens vv mit Grad Δ\Delta und eines Knotens uu, der nicht zu vv benachbart ist
  2. Konstruktion eines Graphen G′G' durch Hinzufügen der Kante uvuv
  3. Berechnung von cM2(G′)−cM2(G)cM_2(G') - cM_2(G) und Beweis, dass diese Differenz positiv ist, was der Extremalität von GG widerspricht

Satz 2 (Proposition 3): Nicht-Nachbarschaft von Knoten mit minimalem Grad

Aussage: Im Extremalgraphen GG sind je zwei Knoten mit minimalem Grad nicht benachbart.

Beweismethode: Durch Widerspruchsbeweis; Annahme, dass benachbarte Knoten mit minimalem Grad existieren, führt zum Widerspruch, dass das Entfernen ihrer Kante cM2cM_2 erhöht.

Satz 3 (Proposition 4): Obergrenze für die Anzahl der Knoten mit maximalem Grad

Beweistechnik:

  1. Auswahl einer Kante zwischen einem Knoten mit maximalem Grad und einem Knoten mit minimalem Grad zum Entfernen
  2. Analyse der Auswirkung des Kantenentfernens auf den cM2cM_2-Wert
  3. Etablierung einer quadratischen Ungleichung bezüglich kk
  4. Lösung zur Erlangung der Obergrenzformel

Analyse spezieller Graphklassen

Vollständige Charakterisierung von Graphen mit zwei verschiedenen Graden (Proposition 5)

Für zusammenhängende Graphen der Ordnung nn mit maximalem Grad n−1n-1 und zwei verschiedenen Graden wird bewiesen: cM2(G)≤k(n−k)((n−1)2−k2)cM_2(G) \leq k(n-k)((n-1)^2 - k^2) Gleichheit gilt genau dann, wenn G=Kk+K‾n−kG = K_k + \overline{K}_{n-k}.

Analyse von Graphen mit drei verschiedenen Graden (Proposition 7)

Mit Hilfe der in Lemma 6 etablierten Ungleichungswerkzeuge wird eine Fallunterscheidung für Graphen mit drei verschiedenen Graden durchgeführt. In jedem Fall wird bewiesen, dass eine optimalere Kt+K‾n−tK_t + \overline{K}_{n-t}-Struktur existiert.

Experimentelle Einrichtung

Rechenmethode

Verwendung von Computersoftware zur Durchführung einer exhaustiven Berechnung für Graphen mit zwei verschiedenen Graden im Bereich 5≤n≤1495 \leq n \leq 149, um die optimalen kk-Werte für jedes nn zu bestimmen.

Datenverifikation

Vergleich der berechneten kk-Wertfolge mit der Datenbank „The On-Line Encyclopedia of Integer Sequences".

Experimentelle Ergebnisse

Hauptrechenergebnisse

Tabelle 1 zeigt die optimalen kk-Werte für nn von 5 bis 149, beispielsweise:

  • n=5n=5: k=2k=2
  • n=10n=10: k=4k=4
  • n=20n=20: k=8k=8
  • n=50n=50: k=19k=19
  • n=100n=100: k=39k=39
  • n=149n=149: k=58k=58

Neuheit der Sequenz

Die berechnete Sequenz 2,2,3,3,3,4,4,4,5,5,6,6,6,7,7,8,8,8,9,9,10,10,10,11,11,12,12,12,13,13,13,...2,2,3,3,3,4,4,4,5,5,6,6,6,7,7,8,8,8,9,9,10,10,10,11,11,12,12,12,13,13,13,... existiert nicht in der OEIS-Datenbank, was zeigt, dass dies eine neue Ganzzahlfolge ist.

Theoretische Verifikation

Korollar 2 bestätigt, dass für n≥11n \geq 11 die optimalen kk-Werte die Bedingung 3n10<k<4n10\frac{3n}{10} < k < \frac{4n}{10} erfüllen, was mit den Rechenergebnissen übereinstimmt.

Verwandte Arbeiten

Entwicklung des Zagreb-Index

  1. Klassische Zagreb-Indizes: Der zweite Zagreb-Index M2(G)=∑uv∈E(G)dudvM_2(G) = \sum_{uv \in E(G)} d_u d_v ist ein klassischer Index in der chemischen Graphentheorie
  2. Geometrische Methoden: Die von Gutman eingeführte geometrische Methode bietet neue Perspektiven für die Untersuchung gradbasisierter topologischer Indizes
  3. Komplementäre Indizes: Der CSZ-Index wurde in mehreren Arbeiten unabhängig unter verschiedenen Namen (Nano-Zagreb-Index, F-Minus-Index usw.) eingeführt

Extremale Graphentheorie

Die Forschungsmethoden dieser Arbeit folgen klassischen Techniken der extremalen Graphentheorie, insbesondere der Methode der Graphtransformation zur Analyse von Veränderungen topologischer Indizes.

Schlussfolgerungen und Diskussion

Hauptschlussfolgerungen

  1. Bestätigung von Struktureigenschaften: Beweis der zwei Schlüsselstruktureigenschaften, die in der Furtula-Oz-Vermutung erwähnt werden
  2. Etablierung von Quantitätsbeschränkungen: Bereitstellung einer strengen mathematischen Obergrenze für die Anzahl der Knoten mit maximalem Grad
  3. Vollständige Lösung für Spezialfälle: Vollständige Verifikation der Vermutung für Graphen mit zwei und drei verschiedenen Graden

Einschränkungen

  1. Vollständiger Beweis für den allgemeinen Fall: Für allgemeine zusammenhängende Graphen bleibt die Vermutung unvollständig bewiesen
  2. Fehlende exakte Formel: Die exakte Funktionsform von kk als Funktion von nn ist noch unbekannt
  3. Begrenzte Rechenbereiche: Derzeit sind nur Berechnungen bis n=149n=149 durchgeführt

Zukünftige Richtungen

  1. Vollständiger Beweis: Suche nach einem vollständigen mathematischen Beweis der Furtula-Oz-Vermutung
  2. Asymptotisches Verhalten: Untersuchung der asymptotischen Eigenschaften und des Grenzwerts von k/nk/n
  3. Algorithmusoptimierung: Entwicklung effizienterer Algorithmen zur Berechnung größerer nn-Werte
  4. Verallgemeinerte Forschung: Verallgemeinerung der Methoden auf andere Arten topologischer Indizes

Tiefgreifende Bewertung

Stärken

  1. Solide theoretische Beiträge: Bereitstellung mehrerer strenger mathematischer Beweise, die das Verständnis der Extremaleigenschaften des CSZ-Index erheblich voranbringen
  2. Starke Methodische Innovation: Kombination von Graphtransformationstechniken und Ungleichungsanalyse mit allgemeiner Anwendbarkeit der Beweismethoden
  3. Detaillierte Rechnerarbeit: Umfangreiche Rechnerverifikation bietet starke Unterstützung für die theoretische Analyse
  4. Klare und normgerechte Darstellung: Präzise Satzformulierungen, klare Beweislogik und Einhaltung mathematischer Schreibkonventionen

Mängel

  1. Unvollständige Lösung der Kernvermutung: Obwohl wichtige unterstützende Ergebnisse bereitgestellt werden, fehlt der vollständige Beweis der Furtula-Oz-Vermutung
  2. Begrenzte technische Tiefe: Hauptsächliche Verwendung relativ elementarer Graphentheorietechniken; möglicherweise sind tiefere mathematische Werkzeuge erforderlich
  3. Unzureichender Anwendungshintergrund: Weniger Diskussion über die spezifische Bedeutung des CSZ-Index in chemischen Anwendungen

Einflussfähigkeit

  1. Theoretischer Wert: Bereitstellung neuer theoretischer Ergebnisse für extremale Graphentheorie und chemische Graphentheorie
  2. Methodischer Wert: Beweistechniken können auf die Untersuchung anderer topologischer Indizes verallgemeinert werden
  3. Rechnerischer Wert: Bereitgestellte Daten und Sequenzen haben Referenzwert für nachfolgende Forschungen

Anwendungsszenarien

Die Methoden und Ergebnisse dieser Arbeit sind anwendbar auf:

  1. Untersuchung molekularer Deskriptoren in der chemischen Graphentheorie
  2. Theoretische Analyse in der extremalen Graphentheorie
  3. Optimierungsprobleme gradbasisierter topologischer Indizes
  4. Kombinatorische Optimierung von Graphstrukturen

Literaturverzeichnis

Die Arbeit zitiert 15 relevante Literaturquellen, die Molekulardeskriptoren, Graphentheoriegrundlagen, Zagreb-Index-Theorie und andere Aspekte abdecken. Das 2025er Papier von Furtula und Oz bildet die direkte Grundlage dieser Forschung.