On a Conjecture Concerning the Complementary Second Zagreb Index

Basic Information

• Paper ID: 2501.01295
• Title: On a Conjecture Concerning the Complementary Second Zagreb Index
• Authors: Hicham Saber, Tariq Alraqad, Akbar Ali, Abdulaziz M. Alanazi, Zahid Raza
• Classification: math.CO (Combinatorics)
• Submission Date: Submitted to arXiv on January 2, 2025
• Paper Link: https://arxiv.org/abs/2501.01295

Abstract

This paper investigates extremal problems concerning the complementary second Zagreb index of graphs. The complementary second Zagreb index 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 vertex $u$ in graph $G$. The authors conduct an in-depth study of a conjecture proposed by Furtula and Oz, which asserts that among all connected graphs of order $n$, the graph $G^*$ maximizing $cM_2$ is the join of a complete graph $K_k$ and its complement $\overline{K}_{n-k}$, with $k<\lceil n/2 \rceil$.

Research Background and Motivation

Problem Background

1. Importance of Molecular Descriptors: Molecular descriptors are fundamental tools for virtual screening of molecular libraries and prediction of physicochemical properties. Descriptors defined through molecular graphs in chemical graph theory are termed topological indices.
2. Degree-Based Topological Indices: Topological indices defined on vertex degrees are widely applied in chemical graph theory. The complementary second Zagreb index (CSZ index) is a recently proposed novel degree-based topological index.
3. Extremal Problems: Determining graph structures that achieve extremal values of topological indices under given constraints is an important problem in graph theory with both theoretical and practical significance.

Research Motivation

1. Theoretical Refinement: Furtula and Oz proposed a conjecture in 2025 regarding the extremal graph structure for the CSZ index, but a rigorous mathematical proof was lacking.
2. Computational Complexity: Determining the number of maximum degree vertices $k$ in the extremal graph as a function of $n$ is considered "far from trivial," requiring novel theoretical tools and computational methods.
3. Practical Value: Understanding the extremal properties of the CSZ index is significant for chemical graph theory and molecular design.

Core Contributions

The main contributions of this paper include:

1. Proof of Maximum Degree Property: Establishes that the maximum degree of a connected $n$-vertex graph $G^*$ maximizing $cM_2$ is $n-1$.
2. Characterization of Minimum Degree Vertices: Proves that any two minimum degree vertices in $G^*$ are non-adjacent.
3. Upper Bound on Maximum Degree Vertices: Establishes that the number $k$ of maximum degree vertices in $G^*$ satisfies: $k \leq -\frac{2}{3}n+\frac{3}{2}+\frac{1}{6}\sqrt{52n^2-132n+81} < \frac{5352n}{10000}$
4. Verification for Special Graph Classes: Proves the correctness of the Furtula-Oz conjecture for biregular and triregular graphs.
5. Computational Data: Provides computational results for biregular graphs with $5 \leq n \leq 149$, finding that the resulting sequence does not exist in the Online Encyclopedia of Integer Sequences.

Detailed Methodology

Problem Formulation

Investigate the structural properties of graphs that maximize the complementary second Zagreb index $cM_2(G) = \sum_{uv\in E(G)}|(d_u(G))^2-(d_v(G))^2|$ among all connected graphs of order $n$.

Core Theorems and Proof Methods

Theorem 1 (Proposition 2): Maximum Degree Property

Statement: If graph $G$ has the maximum $cM_2$ value among all connected graphs of order $n$ with $n \geq 4$, then the maximum degree of $G$ is $n-1$.

Proof Strategy:

1. Assume maximum degree $\Delta < n-1$; select a vertex $v$ of degree $\Delta$ and a vertex $u$ non-adjacent to $v$
2. Construct graph $G'$ by adding edge $uv$
3. Calculate $cM_2(G') - cM_2(G)$ and prove this difference is positive, contradicting the extremality of $G$

Theorem 2 (Proposition 3): Non-Adjacency of Minimum Degree Vertices

Statement: In the extremal graph $G$, any two minimum degree vertices are non-adjacent.

Proof Method: By contradiction, assuming adjacent minimum degree vertices exist, removing the edge between them increases $cM_2$.

Theorem 3 (Proposition 4): Upper Bound on Maximum Degree Vertices

Proof Technique:

1. Select edges connecting maximum and minimum degree vertices for removal
2. Analyze the impact of edge removal on $cM_2$
3. Establish a quadratic inequality in $k$
4. Solve to obtain the upper bound formula

Analysis of Special Graph Classes

Complete Characterization for Biregular Graphs (Proposition 5)

For $n$-vertex biregular connected graphs with maximum degree $n-1$, it is proven that: $cM_2(G) \leq k(n-k)((n-1)^2 - k^2)$ with equality if and only if $G = K_k + \overline{K}_{n-k}$.

Analysis for Triregular Graphs (Proposition 7)

Using the inequality tools established in Lemma 6, triregular graphs are classified and analyzed, proving that in each case there exists a superior $K_t + \overline{K}_{n-t}$ structure.

Experimental Setup

Computational Method

Computer software is used to exhaustively compute the optimal $k$ values for biregular graphs with $5 \leq n \leq 149$.

Data Verification

The computed sequence of $k$ values is compared against the "The On-Line Encyclopedia of Integer Sequences" database.

Experimental Results

Main Computational Results

Table 1 presents the optimal $k$ values for $n$ ranging from 5 to 149, for example:

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

Novelty of the Sequence

The computed sequence $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,...$ does not exist in the OEIS database, indicating this is a new integer sequence.

Theoretical Verification

Corollary 2 confirms that for $n \geq 11$, the optimal $k$ value satisfies $\frac{3n}{10} < k < \frac{4n}{10}$, consistent with computational results.

Related Work

Development of Zagreb Indices

1. Classical Zagreb Indices: The second Zagreb index $M_2(G) = \sum_{uv \in E(G)} d_u d_v$ is a classical index in chemical graph theory
2. Geometric Methods: The geometric approach introduced by Gutman provides new perspectives for studying degree-based topological indices
3. Complementary Indices: The CSZ index has been independently proposed in multiple studies under different names (nano Zagreb index, F-minus index, etc.)

Extremal Graph Theory

This paper's methodology continues classical techniques in extremal graph theory, particularly methods analyzing topological index changes through graph transformations.

Conclusions and Discussion

Main Conclusions

1. Confirmation of Structural Properties: Proves two key structural properties mentioned in the Furtula-Oz conjecture
2. Establishment of Quantitative Constraints: Provides rigorous mathematical upper bounds on the number of maximum degree vertices
3. Complete Resolution for Special Cases: Fully verifies the correctness of the conjecture for biregular and triregular graphs

Limitations

1. Incomplete Proof for General Case: The conjecture remains unproven for general connected graphs
2. Absence of Exact Formula: The exact functional form of $k$ as a function of $n$ remains unknown
3. Limited Computational Range: Current computations extend only to $n=149$

Future Directions

1. Complete Proof: Seek a complete mathematical proof of the Furtula-Oz conjecture
2. Asymptotic Behavior: Study the asymptotic properties and limiting behavior of $k/n$
3. Algorithm Optimization: Develop more efficient algorithms to compute cases with larger $n$
4. Generalization: Extend the methods to other types of topological indices

In-Depth Evaluation

Strengths

1. Solid Theoretical Contributions: Provides multiple rigorous mathematical proofs that significantly advance understanding of CSZ index extremal properties
2. Strong Methodological Innovation: Combines graph transformation techniques with inequality analysis, yielding generally applicable proof methods
3. Detailed Computational Work: Large-scale computational verification provides strong support for theoretical analysis
4. Clear and Rigorous Writing: Theorems are precisely stated, proofs are logically clear, and the work adheres to mathematical writing standards

Weaknesses

1. Core Conjecture Incompletely Resolved: While providing important supporting results, a complete proof of the Furtula-Oz conjecture remains lacking
2. Limited Technical Depth: Primarily employs relatively elementary graph-theoretic techniques; deeper mathematical tools may be needed
3. Insufficient Application Context: Limited discussion of the specific significance of the CSZ index in chemical applications

Impact

1. Theoretical Value: Provides new theoretical results for extremal graph theory and chemical graph theory
2. Methodological Value: Proof techniques are generalizable to research on other topological indices
3. Computational Value: Provided data and sequences serve as reference material for subsequent research

Applicable Scenarios

The methods and results in this paper are applicable to:

1. Molecular descriptor research in chemical graph theory
2. Theoretical analysis in extremal graph theory
3. Optimization problems for degree-based topological indices
4. Combinatorial optimization of graph structures

References

The paper cites 15 relevant references covering molecular descriptors, graph theory fundamentals, Zagreb index theory, and other related areas, with the 2025 paper by Furtula and Oz serving as the direct foundation for this research.