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

補完第二ザグレブ指数に関する予想について

基本情報

論文ID: 2501.01295
タイトル: On a Conjecture Concerning the Complementary Second Zagreb Index
著者: Hicham Saber, Tariq Alraqad, Akbar Ali, Abdulaziz M. Alanazi, Zahid Raza
分類: math.CO（組合数学）
投稿日時: 2025年1月2日（arXivへ）
論文リンク: https://arxiv.org/abs/2501.01295

摘要

本論文は、グラフの補完第二ザグレブ指数の極値問題を研究している。補完第二ザグレブ指数は $cM_2(G)=\sum_{uv\in E(G)}|(d_u(G))^2-(d_v(G))^2|$ と定義され、ここで $d_u(G)$ はグラフ $G$ における頂点 $u$ の次数を表す。著者らはFurtula と Ozが提唱した予想を深く研究した。その予想は、すべての $n$ 次連結グラフの中で $cM_2$ を最大化するグラフ $G^*$ が完全グラフ $K_k$ とその補グラフ $\overline{K}_{n-k}$ の結合であり、 $k<\lceil n/2 \rceil$ を満たすと主張している。

研究背景と動機

問題背景

分子記述子の重要性: 分子記述子は分子ライブラリーの仮想スクリーニングと分子の物理化学的性質の予測における基本的なツールであり、化学グラフ理論では分子グラフを通じて定義される記述子をトポロジカル指数と呼ぶ。
次数ベースのトポロジカル指数: 頂点の次数に基づいて定義されるトポロジカル指数は化学グラフ理論で広く応用されている。補完第二ザグレブ指数（CSZ指数）は最近提案された新しい次数ベースのトポロジカル指数である。
極値問題: 与えられた制約条件下でトポロジカル指数を極値化するグラフ構造を決定することは、グラフ理論における重要な問題であり、理論的および応用的価値を有する。

研究動機

理論の完成: FurturaとOzが2025年に提唱したCSZ指数の極値グラフ構造に関する予想は、厳密な数学的証明が不足している。
計算複雑性: 極値グラフにおける最大次数頂点の数 $k$ を $n$ の関数として決定することは「決して容易ではない」と考えられており、新しい理論的ツールと計算方法が必要である。
応用価値: CSZ指数の極値性質を理解することは、化学グラフ理論と分子設計に重要な意義を持つ。

核心的貢献

本論文の主な貢献は以下の通りである：

極値グラフの最大次数性質の証明: $cM_2$ を最大化する連結 $n$ 次グラフ $G^*$ の最大次数が $n-1$ であることを証明した。
最小次数頂点の隣接性質の解明: $G^*$ における任意の2つの最小次数頂点が隣接していないことを証明した。
最大次数頂点数の上界の確立: $G^*$ における最大次数頂点の数 $k$ が以下を満たすことを証明した： $k \leq -\frac{2}{3}n+\frac{3}{2}+\frac{1}{6}\sqrt{52n^2-132n+81} < \frac{5352n}{10000}$
特殊グラフクラスの予想検証: 二次グラフと三次グラフのクラスに対してFurtula-Oz予想の正当性を証明した。
計算データの提供: コンピュータソフトウェアを用いて $5 \leq n \leq 149$ の範囲における二次グラフの場合の $k$ 値を計算し、得られた数列が整数数列百科事典に存在しないことを発見した。