关于图的指数Randi?指数及其应用

《Discrete Applied Mathematics》：On the exponential Randi? index of graphs and its applications

　　

摘要

在众多基于度的分子描述符中，Randi? 指数因其强大的化学适用性而成为使用最广泛的指数之一。对于一个图 G，Randi? 指数定义为 R(G)=∑vivj∈E(G)1/(di·dj)，其中 di 表示顶点 vi 的度。

为了增强该描述符的区分能力，Rada 于 2019 年引入了 Randi? 指数的指数版本。图 G 的指数 Randi? 指数定义为 ER(G)=∑vivj∈E(G)e^(1/(di·dj))。

在本文中，我们证明了每当向 G 中添加一条边时，ER 指数严格递增——这是分析其极值行为的一个关键性质。在此基础上，我们证明了在所有给定阶数和给定色数的图中，Turán 图唯一地使 ER 指数达到最大值。这一结果为指数版本的指数建立了清晰而刚性的极值结构，与经典的 Randi? 指数形成对比：后者的极值行为在同一限制下更为复杂，且不具有相同的结构唯一性。此外，我们研究了给定阶数和给定最大度的树中关于 ER 指数的最大树结构。最后，我们通过相关性分析和与其他指数型基于度的拓扑指数进行比较，评估了 ER 指数的化学相关性及其预测性能。

引言

设 G=(V,E) 是一个简单图，顶点集为 V(G)={v1,v2,…,vn}，边集为 E(G)，其中 |V(G)|=n，|E(G)|=m。对于顶点 vi∈V(G)，其邻域记为 NG(vi)={vj∈V(G)∣vivj∈E(G)}，其度为 di=dG(vi)=|NG(vi)|；我们用 Δ 表示 G 的最大度。对于任意两个顶点 vi,vj∈V(G)，vi 与 vj 在 G 中的距离记为 dG(vi,vj)。对于一条边 vivj∈E(G)，删除边 vivj 后所得的图记为 G?vivj。类似地，当 vivj?E(G) 时，添加边 vivj 后所得的图记为 G+vivj。完全 r 部图是指其顶点集可以被划分为 r 个不相交的独立集（称为部）的图，其中两个顶点相邻当且仅当它们属于不同的部；若各部的大小依次为 n1,n2,…,nr，且 n1≥n2≥?≥nr，则将该图记为 Kn1,n2,…,nr。Turán 图记为 T(n,r)，它是 n 个顶点上的一个特殊完全 r 部图，其各部大小尽可能相等，即若各部大小为 n1,n2,…,nr，且 n1≥n2≥?≥nr，则 ∑ni=n，且对所有 i,j 均有 |ni?nj|≤1。无环连通图称为树。度为一的顶点称为悬挂顶点（或简称叶），与该顶点相关联的边称为悬挂边。度至少为三的顶点称为分支顶点。G 中长度至少为 1 的一条路径 P=v1v2?vk，如果它的一个端点（v1 或 vk）是悬挂顶点，而另一个端点的度至少为 3，且所有中间顶点（若有）的度恰好为 2，则称该路径为悬挂路径。在本文中，Pn 和 Sn 分别表示 n 个顶点上的路径图和星图。

在有机化学和理论化学中，一个重要的目标是理解分子结构如何影响其可测量的物理和化学性质。图论为此提供了一个有效的框架：将分子表示为图，其中顶点代表原子，边代表化学键。为了定量描述分子结构并对结构—性质关系建模，已引入了大量图论指数。

Randi? 指数是其中最常用的基于度的描述符之一。它由 Milan Randi? 于 1975 年 [45] 提出，作为描述分子分支的工具。对于顶点集 V(G)={v1,v2,…,vn}、边集 E(G) 的图 G，Randi? 指数定义为 R(G)=∑vivj∈E(G)1/(di·dj)，其中 di 表示顶点 vi 的度。Randi? 观察到该指数与烷烃的若干物化性质之间存在强相关性，这使其在化学和药理学中得到广泛应用。

作为一种自然推广，广义 Randi? 指数随后被提出 [6]。对于实参数 α，它定义为 Rα(G)=∑vivj∈E(G)(di·dj)^α。

R 和 Rα 的数学行为已被深入研究。例如，Bollobás 和 Erd?s [6] 证明星图在所有连通图中使 R 最小，而 Caporossi 等人 [7] 证明路径图在所有树中使 R 最大。关于 Rα 的进一步极值结果和相关贡献可见于 [4]、[21]、[22]、[23]、[27]、[33]、[35]、[36]、[38]、[40]、[49]、[51]。

为了增强基于度的指数区分分子结构的能力，Rada [43] 引入了若干经典指数的指数版本。这一想法自提出以来引起了广泛关注，并在各种情境下被研究 [11]、[12]、[13]、[14]、[15]、[17]、[18]、[19]、[20]、[30]。在本工作中，我们关注指数 Randi? 指数，其定义为 ER(G)=∑vivj∈E(G)e^(1/(di·dj))。

ER 指数的若干极值性质已经为人所知。Cruz 等人 [10] 证明在所有树中，路径图取到 ER 的最大值；而 Rada [43] 证明星图取到最小值。进一步的研究针对更广泛的图类考察了 ER 指数，包括化学树 [5]、准树 [42] 和单环图 [39]，其中极值结构被完全刻画。

数学化学中的一个核心问题是在给定图类中确定极值图。色数固定的图是这样一个重要图类，文献中已为若干拓扑指数建立了极值结果 [2]、[3]、[8]、[9]、[17]、[29]、[34]、[37]。特别地，Li 和 Shi [34] 建立了连通图的 Randi? 指数关于其阶数和色数的下界。然而，据我们所知，在所有色数固定的连通图中确定 Randi? 指数最大的连通图这一问题尚未被研究。使用 Sage 我们观察到，最大图通常不唯一。更确切地说，在色数固定的连通图中，可能有若干个非同构图取得相同的最大 Randi? 指数。例如，在阶数为 8、色数为 3 的连通图中，有多个图取得最大值，如图 1 所示。这自然引出如下问题：

指数 Randi? 指数是否表现出类似的非唯一极大行为，还是在色数约束下存在唯一的最大化图？

受此问题启发，本文研究了阶数和色数固定的图的 ER 指数的极大性质。此外，我们研究给定阶数和给定最大度的树的 ER 指数行为，并考察相应的极大树结构。

本文其余部分安排如下：第 2 节考察加边对 ER 指数的影响；第 3 节证明在所有阶数和色数固定的图中，Turán 图唯一地取到 ER 指数的最大值；第 4 节致力于为给定阶数和给定最大度的树的 ER 指数建立上界，并刻画相应的极值结构；第 5 节通过相关性分析和比较预测性能研究，考察 ER 指数的化学意义；最后，第 6 节总结全文并提出若干评述及未来研究方向。

第 2 节：加边对指数 Randi? 指数的影响

在本节中，我们首先证明向 G 中添加一条边时，ER 指数严格递增。

定理 2.1 设 G 是阶数 n≥3 的连通非完全图。若 vivj?E(G)，则 ER(G+vivj)>ER(G)。

证明：设 vivj?E(G)。不失一般性，设 di≥dj。由于 G 连通，故 di,dj≥1。于是
ER(G+vivj)?ER(G)=∑_{vk:vivk∈E(G)}(e^(1/((di+1)dk))?e^(1/(didk))) + ∑_{vk:vjvk∈E(G)}(e^(1/((dj+1)dk))?e^(1/(djdk))) + e^(1/((di+1)(dj+1)))。

我们证明如下断言：

断言 1 ∑_{vk:vivk∈E(G)}(e^(1/((di+1)dk))?e^(1/(didk)))>?1/2。

断言 1 的证明：我们通过以下四个步骤构造证明。（原文此处为"我们按如下四步构造证明"，后续步骤在提供的文本中被截断。）

第 3 节：以顶点数和色数表示的指数 Randi? 指数的上界

在本节中，我们建立以顶点数和色数表示的指数 Randi? 指数的上界，并刻画达到该上界的图。为此需要如下结果：

引理 3.1 对 0≤x≤1/2，有 (i) e^x≤1+2x，(ii) e^x≤1+x+x^2。

证明：考虑两个函数 f(x)=1+x+x^2?e^x（0≤x≤1/2），g(x)=1+2x?e^x（0≤x≤1/2）。则 f′(x)=1+2x?e^x，g′(x)=2?e^x>0，因为 0≤x≤1/2。因此 g(x) 在 0≤x≤1/2 上为增函数，故 g(x)≥g(0)=0，即 e^x≤1+2x。这（原文证明在此处被截断）。

第 4 节：以最大度表示的指数 Randi? 指数的上界

在本节中，我们给出给定阶数和给定最大度的树的 ER 指数的上界，并刻画相应的极值树。我们从如下有用的引理开始。

引理 4.1 设 h(x)=e^(1/(ax))?e^(1/(bx))，x≥1，a,b>0。则函数 h(x) 具有如下单调性：
(i) 若 ab，则 h(x) 在 [1,∞) 上严格递增。

证明：对 x 求导得 h′(x)=?(1/(2a))x^(?3/2)e^(1/(ax))+(1/(2b))x^(?3/2)e^(1/(bx))=(1/(2x^(3/2)))·(e^(1/(bx))/b ? e^(1/(ax))/a)。若 a
第 5 节：化学意义

除数学研究外，考察一个拓扑指数是否传递有意义的化学信息同样至关重要。randi? 和 trinajsti? [46] 指出，分子描述符的意义可以通过考察其与实验测定的物化性质之间的联系来评估。他们进一步建议以辛烷异构体作为初始验证新提出指数的基准数据集。采用该方法的若干研究可见于（原文此处被截断）。

结论

在本文中，我们研究了在所有色数固定的图中取到 er 指数最大值的极值图，并证明 turán 图唯一地取得该最大值。这一结果表明，指数版本的指数与经典 randi? 指数表现出根本不同的极值行为——后者的极值行为在同一约束下要复杂得多。

此外，我们研究了在阶数和最大度受限条件下的树……（原文结论部分被截断。）

利益冲突声明：作者声明不存在已知的竞争财务利益或个人关系可能影响本文所报告的工作。

致谢：k. c. das 获得韩国政府国家研究基金会资助（项目编号 rs-2026-25475577）。kinkar chandra das｜jayanta bera e^(1 (b)（原文证明在此处被截断）。 第 5 节：化学意义 除数学研究外，考察一个拓扑指数是否传递有意义的化学信息同样至关重要。randi? 和 trinajsti? [46] 指出，分子描述符的意义可以通过考察其与实验测定的物化性质之间的联系来评估。他们进一步建议以辛烷异构体作为初始验证新提出指数的基准数据集。采用该方法的若干研究可见于（原文此处被截断）。 结论 在本文中，我们研究了在所有色数固定的图中取到 er 指数最大值的极值图，并证明 turán 图唯一地取得该最大值。这一结果表明，指数版本的指数与经典 randi? 指数表现出根本不同的极值行为——后者的极值行为在同一约束下要复杂得多。 此外，我们研究了在阶数和最大度受限条件下的树……（原文结论部分被截断。） 利益冲突声明：作者声明不存在已知的竞争财务利益或个人关系可能影响本文所报告的工作。 致谢：k. c. das 获得韩国政府国家研究基金会资助（项目编号 rs-2026-25475577）。kinkar chandra das｜jayanta>
第 5 节：化学意义

除数学研究外，考察一个拓扑指数是否传递有意义的化学信息同样至关重要。randi? 和 trinajsti? [46] 指出，分子描述符的意义可以通过考察其与实验测定的物化性质之间的联系来评估。他们进一步建议以辛烷异构体作为初始验证新提出指数的基准数据集。采用该方法的若干研究可见于（原文此处被截断）。

结论

在本文中，我们研究了在所有色数固定的图中取到 er 指数最大值的极值图，并证明 turán 图唯一地取得该最大值。这一结果表明，指数版本的指数与经典 randi? 指数表现出根本不同的极值行为——后者的极值行为在同一约束下要复杂得多。

此外，我们研究了在阶数和最大度受限条件下的树……（原文结论部分被截断。）

利益冲突声明：作者声明不存在已知的竞争财务利益或个人关系可能影响本文所报告的工作。

致谢：k. c. das 获得韩国政府国家研究基金会资助（项目编号 rs-2026-25475577）。kinkar chandra das｜jayanta bera>