两图运算后Sombor指数的上界

The Upper Bound of Sombor Index After Two Graph Operations

摘要

Sombor指数是基于顶点度引入的一种新的化学拓扑指数。本文研究了两个有限简单的连通图经过连接运算、笛卡尔积运算、冠运算、字典序积运算、对称差运算后的Sombor指数，并且刻画了其极图。首先，对每种运算后表达式的边进行了分类。然后，利用顶点的最大度并结合不等式放缩，给出了各运算图Sombor指数上界的估值不等式。最后，证明了取得Sombor指数上界的条件为两图都是正则图。

Abstract

Sombor index is a new chemical topological index introduced based on vertex degree. The Sombor index of two finite simple connected graphs is studied after five graph operations （i.e.， connection operation， Cartesian product operation， crown operation， dictionary order product operation， and symmetric difference operation）， and their extremal graphs are described. Firstly， the edges of the expressions after each operation are classified. Then a valuation inequality for the upper bound of the Sombor index of the graphs of each operation is given by using the maximum degree of the vertices and the inequality deflation. Finally， the condition of obtaining the upper bound of Sombor index is given to be that both graphs are regular graphs.

Graphical abstract

关键词

Sombor指数的上界 / 连接运算 / 笛卡尔积运算 / 冠运算 / 字典序积运算 / 对称差运算

Key words

upper bound of Sombor index / connection operation / Cartesian product operation / crown operation / dictionary order product operation / symmetrical difference operation

0 引 言

图论是数学的一个重要分支，起源于1736年欧拉提出的柯尼斯堡问题。几何拓扑学是图论的一个数学分支。拓扑指数起源于1947年，利用拓扑指数可以构建QSAR/QSPR模型，研究分子结构图的相关性质，对化合物性质的评估与预测有着非常重要的作用。学者们已提出了200余种拓扑指数，用来刻画分子结构图的各种化学、数学性质。拓扑指数可以与化学、物理、生物、计算机等结合，把相应的变量看做点和边，通过计算可以优化模型的极值，在实际的生产生活中有着极其重要的应用。在拓扑指数中，经常研究给定一些参数（如点的个数、边的个数、最大度、最小度、围长等）图的极值问题，包括单圈图、双圈图、三圈图、化学图、烷烃类图、树图等，和对图做细化、加权、连接、剖分等变换以后各种指数的变化，以及图能量的上下界。常见的拓扑指数有Wiener指数、Zagreb指数、Randic'指数、遗忘指数等^［1‐8］。

Gutman提出了Sombor指数，同时还定义了约化Sombor指数和平均Sombor指数^［9］。黄雨飞等^［10］研究了改良Sombor指数，确定了给定参数（最大度、最小度、直径、周长）的图的改良Sombor指数的一些界，且得到了改良Sombor谱半径和谱能量的一些界。Hernández等^［11］刻画了简单图的Sombor指数的极值问题，得到了一般Sombor指数新的最优上界和最优下界，以及Sombor指数与其它相关著名的基于顶点度的拓扑指数之间的不等式关系。李舒超等^［12］采用了对直径进行分类讨论的方法，计算了给定直径的n个顶点树的Sombor指数的界。Liu等^［13］计算了关于化学图的Sombor指数及其在苯类碳氢化合物沸点上的应用。关于Sombor指数的其他研究可参考相关文献^［14-17］。

随着化学图论的快速发展，对于拓扑指数的深入研究已经从一个分子图删边运算、删点运算，延伸到一系列分子图的并、交、差、联、积等运算，比如图的连接运算、笛卡尔积运算、冠运算、字典序积运算、对称差运算等。本文讨论了这些运算之后Sombor指数的上界。

1 预备知识

设G=\left(V,E\right)是一个有限简单连通图,其中,顶点集为V=V(G),\left|V(G)\right|=n_G, \left\{u_{\mathrm{1}},u_{\mathrm{2}},\cdots ,u_{n_G}\right\}∈V\left(G\right), 边集为E=E\left(G\right), \left|E\left(G\right)\right|=m_G, uv是G中的任意一条边, 即uv\in E\left(G\right), 图G的最大度为{\mathrm{\Delta }}_G, 最小度为{\delta }_G, G中顶点v的度为与点v相连的边数的个数, 用d_G\left(v\right)表示。

定义1^［9］ Sombor指数的定义为

SO=SO\left(G\right)=\sum _{uv\in E\left(G\right)}\sqrt[]{{d_u}^{\mathrm{2}}+{d_v}^{\mathrm{2}}}。

定义2^{［18‐19］} 图G和H的连接运算是将G中的每个顶点都连接到H的每个顶点，同时，保持图G和H原有的边不变，记为G\vee H。顶点集为V\left(G\vee H\right)=V\left(G\right)\bigcup V\left(H\right)。 边集为E（G∨H）=E（G）∪E（H）∪｛uv|u∈V（G）， v∈（G）， v∈V（H）｝。

定义3^［20］ 两图的笛卡尔积运算记为G\times H。顶点集为V\left(G\times H\right)=V\left(G\right)\times V\left(H\right)。边集为E（G×H）={(u₁,v₁)(u₂,v₂)|u₁=u₂，且v_{\mathrm{1}}{v}_{\mathrm{2}}∈E\left(H\right)，或者v_{\mathrm{1}}=v_{\mathrm{2}}且\left.u_{\mathrm{1}}{u}_{\mathrm{2}}\in E\left(G\right)\right\}。

定义4^［21］ 图G和H的冠运算由一个G和n_G个H复制得到，并且G的第i个顶点和H的第i个复制的所有顶点相连，得到的图\left(i=\mathrm{1,2},\cdots ,n_G\right)记为G\circ H。顶点集为V\left(G\circ H\right)=V（G）{\cup }_{i=\mathrm{1}}^{n_G}{V}_i(H)。边集为E\left(G\circ H\right)=E_{\mathrm{1}}\bigcup E_{\mathrm{2}}\bigcup E_{\mathrm{3}}。E_{\mathrm{1}}=\left\{e|e\in E\left(G\right)\right\}；E_{\mathrm{2}}=\left\{e|e\in E\left(H\right)\right\}；E_{\mathrm{3}}=\{e=u_i{v}_{ij}\left|u_i\right.∈V（G）v_ij ∈V_i （H），i∈\left\{\mathrm{1,2},\cdots ,n_G\right\}， j\in \left\{\mathrm{1,2},\cdots ,n_H\right\}｝。

定义5^［19］ 两图的字典序积运算记为 G\left[H\right]。顶点集为V\left(G\left[H\right]\right)=V\left(G\right)\times V\left(H\right)。边集为E\left(G\left[H\right]\right)=｛（u₁，v₁）（u₂，v₂）|u₁u₂∈E（G），或者u_{\mathrm{1}}=u_{\mathrm{2}}且\left.v_{\mathrm{1}}{v}_{\mathrm{2}}\in E\left(H\right)\right\}。

若G=P_{\mathrm{2}}，H=P_{\mathrm{3}}，则两图经字典序积运算后如图 1 所示。

定义6^［22］ 两图的对称差运算记为G\oplus H，其中，顶点集为 V\left(G\oplus H\right)=V\left(G\right)\times V\left(H\right)。边集为E\left(G\oplus H\right)=｛（u₁，v₁）（u₂，v₂）|u₁u₂∈E（G），或者v_{\mathrm{1}}{v}_{\mathrm{2}}\in E\left(H\right)，但两者不能同时存在｝。

引理^［23］ 设G和H是两个简单连通图，则

\begin{array}{c}\left|E\left(G\oplus H\right)\right|=\left|E\left(G\right)\right|{\left|V\left(H\right)\right|}^{\mathrm{2}}+\\ \left|E(H)\right|{\left|V(G)\right|}^{\mathrm{2}}-\mathrm{4}\left|E(G)\right|\left|E(H)\right|,\\ d_{G\oplus H}\left(\left(u,v\right)\right)=n_H{d}_G\left(u\right)+\\ n_G{d}_H\left(v\right)-\mathrm{2}{d}_G\left(u\right)d_H\left(v\right)\mathrm{。}\end{array}

2 两图运算后Sombor指数的上界

定理1 设图G和H是两个简单图，则

\begin{array}{c}SO(G_G\vee G_H)\le \sqrt[]{\mathrm{2}}(m_G({\mathrm{\Delta }}_G+n_H)+\\ m_H({\mathrm{\Delta }}_H+n_G)+n_G{n}_H\sqrt[]{({\mathrm{\Delta }}_G+n_H{)}^{\mathrm{2}}+({\mathrm{\Delta }}_H+n_G{)}^{\mathrm{2}}},\end{array}

当且仅当G和H都是正则图时，等号成立。

证明 设V\left(G\right)=\left\{u_{\mathrm{1}},u_{\mathrm{2}},\cdots ,u_{n_G}\right\}，V（H）=\left\{v_{\mathrm{1}},v_{\mathrm{2}},\cdots ,v_{n_H}\right\}，u是G\vee H的一个点，由两图的连接运算定义，得

d_{G\vee H}\left(u\right)=\left\{\begin{array}{c}{d}_G\left(u\right)+\left|V\left(H\right)\right|,u\in V\left(G\right),\\ d_H\left(u\right)+\left|V\left(G\right)\right|,u\in V\left(H\right),\end{array}\right.

故

\begin{array}{c}SO\left(G\vee H\right)=\\ \sum _{uv\in E\left(G\vee H\right)}\sqrt[]{{\left(d_{G\vee H}\left(u\right)\right)}^{\mathrm{2}}+{\left(d_{G\vee H}\left(v\right)\right)}^{\mathrm{2}}}=\\ \sum _{uv\in E\left(G\right)}\sqrt[]{{\left(d_G\left(u\right)+n_H\right)}^{\mathrm{2}}+{\left(d_G\left(v\right)+n_H\right)}^{\mathrm{2}}}+\end{array}

\begin{array}{c}\sum _{uv\in E\left(H\right)}\sqrt[]{{\left(d_H\left(u\right)+n_G\right)}^{\mathrm{2}}+{\left(d_H\left(v\right)+n_G\right)}^{\mathrm{2}}}+\\ \sum _{u\in E\left(G\right),v\in E\left(H\right)}\sqrt[]{{\left(d_G\left(u\right)+n_H\right)}^{\mathrm{2}}+{\left(d_H\left(v\right)+n_G\right)}^{\mathrm{2}}}\le \\ \sum _{uv\in E\left(G\right)}\sqrt[]{{\left({\mathrm{\Delta }}_G+n_H\right)}^{\mathrm{2}}+{\left({\mathrm{\Delta }}_G+n_H\right)}^{\mathrm{2}}}+\\ \sum _{uv\in E\left(H\right)}\sqrt[]{{\left({\mathrm{\Delta }}_H+n_G\right)}^{\mathrm{2}}+{\left({\mathrm{\Delta }}_H+n_G\right)}^{\mathrm{2}}}+\\ \sum _{u\in E\left(G\right),v\in E\left(H\right)}\sqrt[]{{\left({\mathrm{\Delta }}_G+n_H\right)}^{\mathrm{2}}+{\left({\mathrm{\Delta }}_H+n_G\right)}^{\mathrm{2}}}=\\ \sqrt[]{\mathrm{2}}\left(m_G\left({\mathrm{\Delta }}_G+n_H\right)+m_H\left({\mathrm{\Delta }}_H+n_G\right)\right)+\\ n_G{n}_H\sqrt[]{{\left({\mathrm{\Delta }}_G+n_H\right)}^{\mathrm{2}}+{\left({\mathrm{\Delta }}_H+n_G\right)}^{\mathrm{2}}}\mathrm{。}\end{array}

对于任意u\in V\left(G\right), v\in V\left(H\right), d_G\left(u\right)={\mathrm{\Delta }}_G,当d_H\left(v\right)={\mathrm{\Delta }}_H时, 等号成立, 即图G和H都是正则图。

定理2 设图G和H是两个简单图，则

SO\left(G\times H\right)\le \sqrt[]{\mathrm{2}}\left({\mathrm{\Delta }}_G+{\mathrm{\Delta }}_H\right)\left(n_G{m}_H+n_H{m}_G\right)，

当且仅当G和H都是正则图时，等号成立。

证明 设V\left(G\right)=\left\{u_{\mathrm{1}},u_{\mathrm{2}},\cdots ,u_{n_G}\right\}，V\left(H\right)=\left\{v_{\mathrm{1}},v_{\mathrm{2}},\cdots ,v_{n_H}\right\}。 由定义2可以得到两图经过笛卡尔积运算之后点的度，即

d_{G\times H}\left(u,v\right)=d_G\left(u\right)+d_H\left(v\right)，

则

\begin{array}{c}SO\left(G\times H\right)=\sum _{\left(u_{\mathrm{1}},v_{\mathrm{1}}\right)\left(u_{\mathrm{2}},v_{\mathrm{2}}\right)\in E\left(G\times H\right),\left(u_{\mathrm{1}},v_{\mathrm{1}}\right)\ne \left(u_{\mathrm{2}},v_{\mathrm{2}}\right)}\sqrt[]{{\left(d_{G\times H}\left(u_{\mathrm{1}},v_{\mathrm{1}}\right)\right)}^{\mathrm{2}}+{\left(d_{G\times H}\left(u_{\mathrm{2}},v_{\mathrm{2}}\right)\right)}^{\mathrm{2}}}=\\ \sum _{\left(u_{\mathrm{1}},v_{\mathrm{1}}\right)\left(u_{\mathrm{1}},v_{\mathrm{2}}\right)\in E\left(G\times H\right),v_{\mathrm{1}}{v}_{\mathrm{2}}\in E\left(H\right)}\sqrt[]{{\left(d_{G\times H}\left(u_{\mathrm{1}},v_{\mathrm{1}}\right)\right)}^{\mathrm{2}}+{\left(d_{G\times H}\left(u_{\mathrm{1}},v_{\mathrm{2}}\right)\right)}^{\mathrm{2}}}+\\ \sum _{\left(u_{\mathrm{1}},v_{\mathrm{1}}\right)\left(u_{\mathrm{2}},v_{\mathrm{1}}\right)\in E\left(G\times H\right),u_{\mathrm{1}}{u}_{\mathrm{2}}\in E\left(G\right)}\sqrt[]{{\left(d_{G\times H}\left(u_{\mathrm{1}},v_{\mathrm{1}}\right)\right)}^{\mathrm{2}}+{\left(d_{G\times H}\left(u_{\mathrm{2}},v_{\mathrm{1}}\right)\right)}^{\mathrm{2}}}=\\ \sum _{u_{\mathrm{1}}\in V\left(G\right)}\sum _{v_{\mathrm{1}}{v}_{\mathrm{2}}\in E\left(H\right)}\sqrt[]{{\left(d_G\left(u_{\mathrm{1}}\right)+d_H\left(v_{\mathrm{1}}\right)\right)}^{\mathrm{2}}+{\left(d_G\left(u_{\mathrm{1}}\right)+d_H\left(v_{\mathrm{2}}\right)\right)}^{\mathrm{2}}}+\\ \sum _{v_{\mathrm{1}}\in V\left(H\right)}\sum _{u_{\mathrm{1}}{u}_{\mathrm{2}}\in E\left(G\right)}\sqrt[]{{\left(d_G\left(u_{\mathrm{1}}\right)+d_H\left(u_{\mathrm{1}}\right)\right)}^{\mathrm{2}}+{\left(d_G\left(u_{\mathrm{2}}\right)+d_H\left(v_{\mathrm{1}}\right)\right)}^{\mathrm{2}}}\le \\ n_G\sum _{v_{\mathrm{1}}{v}_{\mathrm{2}}\in E\left(H\right)}\left(\sqrt[]{\mathrm{2}}\left({\mathrm{\Delta }}_G+{\mathrm{\Delta }}_H\right)\right)+n_H\sum _{u_{\mathrm{1}}{u}_{\mathrm{2}}\in E\left(G\right)}\left(\sqrt[]{\mathrm{2}}\left({\mathrm{\Delta }}_G+{\mathrm{\Delta }}_H\right)\right)=\\ n_G{m}_H\sqrt[]{\mathrm{2}}\left({\mathrm{\Delta }}_G+{\mathrm{\Delta }}_H\right)+n_H{m}_G\sqrt[]{\mathrm{2}}\left({\mathrm{\Delta }}_G+{\mathrm{\Delta }}_H\right)=\sqrt[]{\mathrm{2}}\left({\mathrm{\Delta }}_G+{\mathrm{\Delta }}_H\right)\left(n_G{m}_H+n_H{m}_G\right)\mathrm{。}\end{array}

对于任意u_i\in V\left(G\right),v_i\in V\left(H\right), 当d_G\left(u_{\mathrm{1}}\right)=d_G\left(u_{\mathrm{2}}\right)={\mathrm{\Delta }}_G, d_H\left(v_{\mathrm{1}}\right)=d_H\left(v_{\mathrm{2}}\right)={\mathrm{\Delta }}_H时, 等号成立, 即图G和H都是正则图。

定理3 设图G和H是两个简单图，则

SO\left(G\circ H\right)\le m_G\sqrt[]{\mathrm{2}}\left({\mathrm{\Delta }}_G+n_H\right)+

n_G{m}_H\sqrt[]{\mathrm{2}}\left({\mathrm{\Delta }}_H+\mathrm{1}\right)+

n_G{n}_H\sqrt[]{{\left({\mathrm{\Delta }}_G+n_H\right)}^{\mathrm{2}}+{\left({\mathrm{\Delta }}_H+\mathrm{1}\right)}^{\mathrm{2}}},

当且仅当G和H都是正则图时，等号成立。

证明 根据冠运算定义，对于点u\in V\left(G\circ H\right)，可以得到u的度为

d_{G\circ H}\left(u\right)=\left\{\begin{array}{ll}{d}_G\left(u\right)+n_H,& \mathrm{当}u\in V\left(G\right),\\ d_H\left(u\right)+\mathrm{1},& \mathrm{当}u\in V\left(G_H\right)\mathrm{。}\end{array}\right.

因此

\begin{array}{c}SO\left(G\circ H\right)=\\ \sum _{e\in E\left(G\circ H\right)}\sqrt[]{{\left(d_{G\circ H}\left(u\right)\right)}^{\mathrm{2}}+{\left(d_{G\circ H}\left(v\right)\right)}^{\mathrm{2}}}=\\ \sum _{e\in E_{\mathrm{1}}}\sqrt[]{{\left(d_G\left(u\right)+n_H\right)}^{\mathrm{2}}+{\left(d_G\left(v\right)+n_H\right)}^{\mathrm{2}}}+\\ n_G\sum _{e\in E_{\mathrm{2}}}\sqrt[]{{\left(d_H\left(u\right)+\mathrm{1}\right)}^{\mathrm{2}}+{\left(d_H\left(v\right)+\mathrm{1}\right)}^{\mathrm{2}}}+\\ \sum _{e\in E_{\mathrm{3}}}\sqrt[]{{\left(d_G\left(u\right)+n_H\right)}^{\mathrm{2}}+{\left(d_H\left(v\right)+\mathrm{1}\right)}^{\mathrm{2}}}\le \\ \sum _{e\in E_{\mathrm{1}}}\sqrt[]{\mathrm{2}}({\mathrm{\Delta }}_G+n_H)+n_G\sum _{e\in E_{\mathrm{2}}}\sqrt[]{\mathrm{2}}({\mathrm{\Delta }}_H+\mathrm{1})+\\ \sum _{e\in E_{\mathrm{3}}}\sqrt[]{({\mathrm{\Delta }}_G+n_H{)}^{\mathrm{2}}+({\mathrm{\Delta }}_H{+\mathrm{1})}^{\mathrm{2}}}=\end{array}

\begin{array}{l}{m}_G\sqrt[]{\mathrm{2}}\left({\mathrm{\Delta }}_G+n_H\right)+n_G{m}_H\sqrt[]{\mathrm{2}}\left({\mathrm{\Delta }}_H+\mathrm{1}\right)+\\ n_G{n}_H\sqrt[]{{\left({\mathrm{\Delta }}_G+n_H\right)}^{\mathrm{2}}+{\left({\mathrm{\Delta }}_H+\mathrm{1}\right)}^{\mathrm{2}}}\mathrm{。}\end{array}

对于任意u_i\in V\left(G\right),v_i\in V\left(H\right), 当d_G\left(u_{\mathrm{1}}\right)=d_G\left(u_{\mathrm{2}}\right)={\mathrm{\Delta }}_G, d_H\left(v_{\mathrm{1}}\right)=d_H\left(v_{\mathrm{2}}\right)={\mathrm{\Delta }}_H时, 等号成立, 即图G和H都是正则图。

定理4 设图G和H是两个简单图，则

SO\left(G\left[H\right]\right)\le \sqrt[]{\mathrm{2}}\left(n_G{m}_H+{n_H}^{\mathrm{2}}{m}_G\right)\left(n_H{\mathrm{\Delta }}_G+{\mathrm{\Delta }}_H\right)，

当且仅当G和H都是正则图时，等号成立。

证明 由定义5可得，两图经过字典序积运算后点的度为

d_{G\left[H\right]}\left(u,v\right)=n_H{d}_G\left(u\right)+d_H\left(v\right)，

则

\begin{array}{c}SO\left(G\left[H\right]\right)=\sum _{\left(u_{\mathrm{1}},v_{\mathrm{1}}\right)\left(u_{\mathrm{2}},v_{\mathrm{2}}\right)\in E\left(G\left[H\right]\right),\left(u_{\mathrm{1}},v_{\mathrm{1}}\right)\ne \left(u_{\mathrm{2}},v_{\mathrm{2}}\right)}\sqrt[]{{\left(d_{G\left[H\right]}\left(u_{\mathrm{1}},v_{\mathrm{1}}\right)\right)}^{\mathrm{2}}+{\left(d_{G\left[H\right]}\left(u_{\mathrm{2}},v_{\mathrm{2}}\right)\right)}^{\mathrm{2}}}=\\ \sum _{\left(u_{\mathrm{1}},v_{\mathrm{1}}\right)\left(u_{\mathrm{1}},v_{\mathrm{2}}\right)\in E\left(G\left[H\right]\right)}\sqrt[]{{\left(d_{G\left[H\right]}\left(u_{\mathrm{1}},v_{\mathrm{1}}\right)\right)}^{\mathrm{2}}+{\left(d_{G\left[H\right]}\left(u_{\mathrm{1}},v_{\mathrm{2}}\right)\right)}^{\mathrm{2}}}+\\ \sum _{\left(u_{\mathrm{1}},v_{\mathrm{1}}\right)\left(u_{\mathrm{2}},v_{\mathrm{2}}\right)\in E\left(G\left[H\right]\right)}\sqrt[]{{\left(d_{G\left[H\right]}\left(u_{\mathrm{1}},v_{\mathrm{1}}\right)\right)}^{\mathrm{2}}+{\left(d_{G\left[H\right]}\left(u_{\mathrm{2}},v_{\mathrm{2}}\right)\right)}^{\mathrm{2}}}=\\ \sum _{u_{\mathrm{1}}\in V\left(G\right)}\sum _{v_{\mathrm{1}}{v}_{\mathrm{2}}\in E\left(H\right)}\left(\sqrt[]{{\left(n_H{d}_G\left(u_{\mathrm{1}}\right)+d_H\left(v_{\mathrm{1}}\right)\right)}^{\mathrm{2}}+{\left(n_H{d}_G\left(u_{\mathrm{1}}\right)+d_H\left(v_{\mathrm{2}}\right)\right)}^{\mathrm{2}}}\right)+\\ \sum _{u_{\mathrm{1}}{u}_{\mathrm{2}}\in E\left(G\right)}\sum _{v_{\mathrm{1}}\in V\left(H\right)}\sum _{v_{\mathrm{2}}\in V\left(H\right)}\left(\sqrt[]{{\left(n_H{d}_G\left(u_{\mathrm{1}}\right)+d_H\left(v_{\mathrm{1}}\right)\right)}^{\mathrm{2}}+{\left(n_H{d}_G\left(u_{\mathrm{2}}\right)+d_H\left(v_{\mathrm{2}}\right)\right)}^{\mathrm{2}}}\right)=\\ n_G\sum _{v_{\mathrm{1}}{v}_{\mathrm{2}}\in E\left(H\right)}\left(\sqrt[]{{\left(n_H{d}_G\left(u_{\mathrm{1}}\right)+d_H\left(v_{\mathrm{1}}\right)\right)}^{\mathrm{2}}+{\left(n_H{d}_G\left(u_{\mathrm{1}}\right)+d_H\left(v_{\mathrm{2}}\right)\right)}^{\mathrm{2}}}\right)+\\ {n_H}^{\mathrm{2}}\sum _{u_{\mathrm{1}}{u}_{\mathrm{2}}\in E\left(G\right)}\left(\sqrt[]{{\left(n_H{d}_G\left(u_{\mathrm{1}}\right)+d_H\left(v_{\mathrm{1}}\right)\right)}^{\mathrm{2}}+{\left(n_H{d}_G\left(u_{\mathrm{2}}\right)+d_H\left(v_{\mathrm{2}}\right)\right)}^{\mathrm{2}}}\right)\le \\ n_G\sum _{v_{\mathrm{1}}{v}_{\mathrm{2}}\in E\left(H\right)}\left(\sqrt[]{{\left(n_H{\mathrm{\Delta }}_G+d_H\left(v_{\mathrm{1}}\right)\right)}^{\mathrm{2}}+{\left(n_H{\mathrm{\Delta }}_G+d_H\left(v_{\mathrm{2}}\right)\right)}^{\mathrm{2}}}\right)+\\ n_H^{\mathrm{2}}\sum _{u_{\mathrm{1}}{u}_{\mathrm{2}}\in E\left(G\right)}\left(\sqrt[]{{\left(n_H{d}_G\left(u_{\mathrm{1}}\right)+{\mathrm{\Delta }}_H\right)}^{\mathrm{2}}+{\left(n_H{d}_G\left(u_{\mathrm{2}}\right)+{\mathrm{\Delta }}_H\right)}^{\mathrm{2}}}\right)\le \\ n_G\sum _{v_{\mathrm{1}}{v}_{\mathrm{2}}\in E\left(H\right)}\left(\sqrt[]{\mathrm{2}}\left(n_H{\mathrm{\Delta }}_G+{\mathrm{\Delta }}_H\right)\right)+{n_H}^{\mathrm{2}}\sum _{u_{\mathrm{1}}{u}_{\mathrm{2}}\in E\left(G\right)}\left(\sqrt[]{\mathrm{2}}\left(n_H{\mathrm{\Delta }}_G+{\mathrm{\Delta }}_H\right)\right)=\\ n_G{m}_H\sqrt[]{\mathrm{2}}\left(n_H{\mathrm{\Delta }}_G+{\mathrm{\Delta }}_H\right)+{n_H}^{\mathrm{2}}{m}_G\sqrt[]{\mathrm{2}}\left(n_H{\mathrm{\Delta }}_G+{\mathrm{\Delta }}_H\right)=\sqrt[]{\mathrm{2}}\left(n_G{m}_H+{n_H}^{\mathrm{2}}{m}_G\right)\left(n_H{\mathrm{\Delta }}_G+{\mathrm{\Delta }}_H\right)\mathrm{。}\end{array}

对于任意u_i\in V\left(G\right),v_i\in V\left(H\right), 当d_G\left(u_{\mathrm{1}}\right)=d_G\left(u_{\mathrm{2}}\right)={\mathrm{\Delta }}_G, d_H\left(v_{\mathrm{1}}\right)=d_H\left(v_{\mathrm{2}}\right)={\mathrm{\Delta }}_H时, 等号成立, 即图G和H都是正则图。

定理 5 设图G和H是两个简单图，则

\begin{array}{c}SO\left(G\oplus H\right)\le \sqrt[]{\mathrm{2}}\left({n_H}^{\mathrm{2}}{m}_G+{n_G}^{\mathrm{2}}{m}_H-\mathrm{4}{m}_G{m}_H\right)\\ \left(n_H{\mathrm{\Delta }}_G+n_G{\mathrm{\Delta }}_H-\mathrm{2}{\mathrm{\Delta }}_G{\mathrm{\Delta }}_H\right),\end{array}

当且仅当G和H都是正则图时，等号成立。

证明 设V\left(G\right)=\{u_{\mathrm{1}},u_{\mathrm{2}},\cdots ,u_{{\mathrm{n}}_{\mathrm{G}}-\mathrm{1}},u_{n_G}\},V(H)=\{v_{\mathrm{1}},v_{\mathrm{2}},\cdots ,v_{{\mathrm{n}}_{\mathrm{H}}-\mathrm{1}},v_{{\mathrm{n}}_{\mathrm{H}}}\}，则图G中顶点的个数为\left|V(G)\right|=n_G，图H中顶点的个数为\left|V(H)\right|=n_H，在运算图中对于任意点\left(u,v\right)\in V\left(G\oplus H\right)，根据对称差运算定义和引理，得

d_{G\oplus H}\left(u,v\right)=n_H{d}_G\left(u\right)+n_G{d}_H\left(v\right)-\mathrm{2}{d}_G\left(u\right)d_H\left(v\right)，

因此

SO\left(G\oplus H\right)=\sum _{\left(u_{\mathrm{1}},v_{\mathrm{1}}\right)\left(u_{\mathrm{2}},v_{\mathrm{2}}\right)\in E\left(G\oplus H\right)}\sqrt[]{{\left(d_{G\oplus H}\left(u_{\mathrm{1}},v_{\mathrm{1}}\right)\right)}^{\mathrm{2}}+{\left(d_{G\oplus H}\left(u_{\mathrm{2}},v_{\mathrm{2}}\right)\right)}^{\mathrm{2}}}=

\sum _{v_{\mathrm{1}}\in V\left(H\right)}\sum _{v_{\mathrm{2}}\in V\left(H\right)}\sum _{u_{\mathrm{1}}{u}_{\mathrm{2}}\in E\left(G\right)}\sqrt[]{{\left(d_{G\oplus H}\left(u_{\mathrm{1}},v_{\mathrm{1}}\right)\right)}^{\mathrm{2}}+{\left(d_{G\oplus H}\left(u_{\mathrm{2}},v_{\mathrm{2}}\right)\right)}^{\mathrm{2}}}+

\sum _{u_{\mathrm{1}}\in V\left(G\right)}\sum _{u_{\mathrm{2}}\in V\left(G\right)}\sum _{v_{\mathrm{1}}{v}_{\mathrm{2}}\in E\left(H\right)}\sqrt[]{{\left(d_{G\oplus H}\left(u_{\mathrm{1}},v_{\mathrm{1}}\right)\right)}^{\mathrm{2}}+{\left(d_{G\oplus H}\left(u_{\mathrm{2}},v_{\mathrm{2}}\right)\right)}^{\mathrm{2}}}-

\sum _{u_{\mathrm{1}}{u}_{\mathrm{2}}\in E\left(G\right)}\sum _{v_{\mathrm{1}}{v}_{\mathrm{2}}\in E\left(H\right)}\sqrt[]{{\left(d_{G\oplus H}\left(u_{\mathrm{1}},v_{\mathrm{1}}\right)\right)}^{\mathrm{2}}+{\left(d_{G\oplus H}\left(u_{\mathrm{2}},v_{\mathrm{2}}\right)\right)}^{\mathrm{2}}}。（1）

根据d_{G\oplus H}\left(u,v\right)=n_H{d}_G\left(u\right)+n_G{d}_H\left(v\right)-\mathrm{2}{d}_G\left(u\right)d_H\left(v\right)，得

\sqrt[]{{\left(d_{G\oplus H}\left(u_{\mathrm{1}},v_{\mathrm{1}}\right)\right)}^{\mathrm{2}}+{\left(d_{G\oplus H}\left(u_{\mathrm{2}},v_{\mathrm{2}}\right)\right)}^{\mathrm{2}}}=

\sqrt[]{{\left(n_H{d}_G\left(u_{\mathrm{1}}\right)+n_G{d}_H\left(v_{\mathrm{1}}\right)-\mathrm{2}{d}_G\left(u_{\mathrm{1}}\right)d_H\left(v_{\mathrm{1}}\right)\right)}^{\mathrm{2}}+{\left(n_H{d}_G\left(u_{\mathrm{2}}\right)+n_G{d}_H\left(v_{\mathrm{2}}\right)-\mathrm{2}{d}_G\left(u_{\mathrm{2}}\right)d_H\left(v_{\mathrm{2}}\right)\right)}^{\mathrm{2}}}\le

\sqrt[]{{\left(n_H{\mathrm{\Delta }}_G+n_G{\mathrm{\Delta }}_H-\mathrm{2}{\mathrm{\Delta }}_G{\mathrm{\Delta }}_H\right)}^{\mathrm{2}}+{\left(n_H{\mathrm{\Delta }}_G+n_G{\mathrm{\Delta }}_H-\mathrm{2}{\mathrm{\Delta }}_G{\mathrm{\Delta }}_H\right)}^{\mathrm{2}}}=\sqrt[]{\mathrm{2}}\left(n_H{\mathrm{\Delta }}_G+n_G{\mathrm{\Delta }}_H-\mathrm{2}{\mathrm{\Delta }}_G{\mathrm{\Delta }}_H\right)\mathrm{。}（2）

将式（2）代入式（1），得

\begin{array}{c}SO\left(G\oplus H\right)\le \\ n_H^{\mathrm{2}}{m}_G\left(\sqrt[]{\mathrm{2}}\left(n_H{\mathrm{\Delta }}_G+n_G{\mathrm{\Delta }}_H-\mathrm{2}{\mathrm{\Delta }}_G{\mathrm{\Delta }}_H\right)\right)+\\ n_G^{\mathrm{2}}{m}_H\left(\sqrt[]{\mathrm{2}}\left(n_H{\mathrm{\Delta }}_G+n_G{\mathrm{\Delta }}_H-\mathrm{2}{\mathrm{\Delta }}_G{\mathrm{\Delta }}_H\right)\right)-\\ \mathrm{4}{m}_{\mathrm{G}}{m}_{\mathrm{H}}(\sqrt[]{\mathrm{2}}(n_{\mathrm{H}}{\mathrm{\Delta }}_G+n_{\mathrm{G}}{\mathrm{\Delta }}_H-\mathrm{2}{\mathrm{\Delta }}_G{\mathrm{\Delta }}_H))=\\ \sqrt[]{\mathrm{2}}\left({n_H}^{\mathrm{2}}{m}_G+{n_G}^{\mathrm{2}}{m}_H-\mathrm{4}{m}_G{m}_H\right)\\ \left(n_H{\mathrm{\Delta }}_G+n_G{\mathrm{\Delta }}_H-\mathrm{2}{\mathrm{\Delta }}_G{\mathrm{\Delta }}_H\right)\mathrm{。}\end{array}

对于任意u_i\in V\left(G\right),v_i\in V\left(H\right), 当d_G\left(u_{\mathrm{1}}\right)=d_G\left(u_{\mathrm{2}}\right)={\mathrm{\Delta }}_G, d_H\left(v_{\mathrm{1}}\right)=d_H\left(v_{\mathrm{2}}\right)={\mathrm{\Delta }}_H时, 等号成立, 即图G和H都是正则图。

3 结 论

本文根据已知的Sombor指数的定义和图的连接运算、笛卡尔积运算、冠运算、字典序积运算、对称差运算，得到了两图经过这些运算之后Sombor指数的上界，并且证明了取得Sombor指数上界的条件为两图都是正则图。

参考文献

[1] 段世杰，李峰.两条奇长路的强乘积精确Wiener指数［J］.数学的实践与认识，2021，51（20）：156-169.

[2] DUAN Shijie， LI Feng.Exact wiener index of the strong product of two odd length paths［J］.Mathematics in Practice and Theory，2021，51（20）：156-169.（in Chinese）

[3] SELVAKUMAR K， GANGAESWARI P， ARUNKUM G.The Wiener index of the zero-divisor graph of a finite commutative ring with unity［J］.Discrete Applied Mathematics，2022，311： 72-84.

[4] LU J， HAFIZ R U M， SAIMA N，et al.The Edge-Weighted Graph Entropy Using Redefined Zagreb Indices［J］.Mathematical Problems in Engineering，2022，2022： 5958913.

[5] BUYANTOGTOKH L， HOROLDAGVA B， DAS K C.On general reduced second zagreb index of graphs［J］. Mathematics， 2022， 10（19）： 3553-3553.

[6] 吕怡妃， 李俊， 黄达含， 等. F-sum图的零阶Randic指数与边度指数［J］. 丽水学院学报， 2019， 41（2）： 1-12.

[7] Yifei LÜ， LI Jun， HUANG Dahan， et al. Zrro randic index and generalized edge-degree index of f-sum graphs［J］. Journal of Lishui University， 2019， 41（2）： 1-12. （in Chinese）

[8] ELUMALAI S， MANSOUR T， ROSTAMI M A. On the bounds of the forgotten topological index［J］. Turkish Journal of Mathematics， 2017， 41（6）： 1687-1702.

[9] 程宇， 邵燕灵. 图的ISDD指数的界［J］. 中北大学学报（自然科学版）， 2022， 43（5）： 385-389.

[10] CHENG Yu， SHAO Yanling. Bounds of ISDD indices of graphs［J］. Journal of North University of China （Natural Science Edition）， 2022， 43（5）： 385-389. （in Chinese）

[11] 孙晓玲， 高玉斌， 杜建伟. 具有 k 个悬挂点的化学图的调和指数［J］. 中北大学学报（自然科学版）， 2018， 39（6）： 633-636.

[12] SUN Xiaoling， GAO Yubin， DU Jianwei. The harmonic index on chemical graphs with k pendant vertices［J］. Journal of North University of China（Natural Science Edition）， 2018， 39（6）： 633-636. （in Chinese）

[13] GUTMAN I. Geometric approach to degree-based topological indices： Sombor indices［J］. Match Communications in Mathematical & in Computer Chemistry， 2021， 86（1）： 11-16.

[14] HUANG Y F， LIU H C. Bounds of modified Sombor index， spectral radius and energy［J］. AIMS Mathematics， 2021， 6（10）： 11263-11274.

[15] HERNÁNDEZ J C， RODRÍGUEZ J M， ROSARIO O， et al. Extremal problems on the general Sombor index of a graph［J］. AIMS Mathematics， 2022， 7（5）： 8330-8343.

[16] LI S C， WANG Z， ZHANG M J. On the extremal Sombor index of trees with a given diameter［J］. Applied Mathematics and Computation， 2022， 416： 126731.

[17] LIU H C， CHEN H L， XIAO Q Q， et al. More on Sombor indices of chemical graphs and their applications to the boiling point of benzenoid hydrocarbons［J］. International Journal of Quantum Chemistry， 2021， 121（17）： e26689.

[18] DENG H Y， TANG Z K， WU R F. Molecular trees with extremal values of Sombor indices［J］. International Journal of Quantum Chemistry， 2021， 121（11）： e26622.

[19] NING W J， SONG Y H， WANG K. More on Sombor index of graphs[J]. Mathematics, 2022, 10(3): 301.

[20] LI Y B， LIU H Q， ZHANG R T. Quasi-tree graphs with the minimal Sombor indices［J］. Czechoslovak Mathematical Journal， 2022， 72（4）： 1227-1238.

[21] SHANG Y L. Sombor index and degree-related properties of simplicial networks［J］. Applied Mathematics and Computation， 2022， 419： 126881.

[22] YEH Y N， GUTMAN I. On the sum of all distances in composite graphs［J］. Discrete Mathematics， 1994， 135（1/3）： 359-365.

[23] HARARY F. Graph theory［M］. Massachusetts： Addison-Wesley， 1971.

[24] DAS K C， XU K， CANGUL I N， et al. On the Harary index of graph operations［J］. Journal of Inequalities and Applications， 2013， 2013： 339.

[25] PATTABIRAMAN K. Inverse sum indeg index of graphs［J］. AKCE International Journal of Graphs and Combinatorics， 2018， 15（2）： 155-167.

[26] KHALIFEH M H， YOUSEFI-AZARI H， ASHRAFI A R. The hyper-Wiener index of graph operations［J］. Computers & Mathematics with Applications， 2008， 56（5）： 1402-1407.

[27] ASHRAFI A R， DOŠLIĆ T， HAMZEH A. The Zagreb coindices of graph operations［J］. Discrete Applied Mathematics， 2010， 158（15）： 1571-1578.

基金资助

国家自然科学基金资助项目(61774137)

山西省回国留学人员科研项目(2022-149)

山西省自然科学基金资助项目(20210302124212)