图运算下的反对称分割指数

The Inverse Symmetric Division Deg Index Under Graph Operation

摘要

分子拓扑指数是分子图的拓扑不变量， 常常用来研究化合物结构与性质之间的关系。反对称分割指数是基于顶点度的一种新型分子拓扑指数。本文研究了两个有限简单连通图经过联、 冠积、 笛卡尔积、 字典序积和对称差的运算所得新图的反对称分割指数和其达到这些上界的极图。首先， 根据联、 冠积、 笛卡尔积、 字典序积和对称差运算的定义， 对这五种运算后表达式的边进行分类。然后， 以顶点的最大度和最小度为基准， 通过放缩法， 对各顶点的度进行合理放缩， 找出各类图运算下的反对称分割指数上界的估值不等式。最后， 证明当两图都为正则图时， 所得图运算的反对称分割指数可取得上界。此研究结果可作为一种预测方法， 对图运算下的其它有关顶点度的拓扑指数的研究具有借鉴意义。

Abstract

Molecular topological indices are topological invariants of molecular graphs， and are often used to study the relationship between structures and properties of compounds. The inverse symmetric division deg index is a new type of molecular topological index based on vertex degree. We studied the inverse symmetric division deg indices of new graphs obtained from two finite simple connected graphs by the operations of Join， Corona product， Cartesian product， Lexicographic and Symmetric， and their extremal graphs reaching these upper bounds. Firstly， the edges of the expression after these five operations were classified according to the definitions of Join， Corona product， Cartesian product， Lexicographic and Symmetric operations. Then， using the maximum and minimum degrees of the vertices， the degree of each vertex was rationally deflated by the deflation method to find out the valuation inequality of the upper bound of the inverse symmetric division deg indices under each type of graph operation. Finally， it was proved that the upper bound of the inverse symmetric division deg index of the resulting graph operations could be obtained when both graphs were regular graphs. The results of this study can be used as a prediction method for other studies on topological indices of vertex degree under graph operations.

Graphical abstract

关键词

图运算 / 反对称分割指数 / 极图 / 界

Key words

graph operation / inverse symmetric division deg index / extremal graph / bound

0 引　言

设图G=\left(V\left(G\right),E\left(G\right)\right)为无向简单连通图， 其中， 顶点集为V\left(G\right)， 边集为 E\left(G\right)。图G中与顶点v相关联的边的个数称为顶点v的度， 记作d_G\left(v\right)， 图G的最大度记为\mathrm{\Delta }， 最小度记为\delta， 对于其他未定义的术语和概念可参阅文献［1］。

2010年， Vukičević^［2］首次提出了图G的对称分割指数（SDD指数）上下界的相关问题。对称分割指数界值相关研究成果可查阅文献［3‐5］。在此基础上， Ghorbani等^［6］在2021年提出了一种新的拓扑指数——图G的反对称分割指数（ISDD指数）， 其定义为ISDD\left(G\right)=\sum _{uv\in E\left(G\right)}\frac{d_G\left(u\right)d_G\left(v\right)}{d_G^{\mathrm{2}}\left(u\right)+d_G^{\mathrm{2}}\left(v\right)}， 并探讨了对称分割指数和反对称分割指数的一些上下界， 给出了二者之间不等式的关系。随后， Albalahi等^［7］刻画了具有最大和最小反对称分割指数的单圈图。

随着图论的发展， 图运算可将所提供的化学图合成一个新的图， 各种拓扑指数的图运算变成了一个研究热点， 并在化学、 生物学、 网络科学等领域广泛应用。De、 Pattabiraman、 Imran等^［8‐10］分别讨论了F指数、 逆和度指数和Mostar指数的图运算， 并给出了上下界。其它相关结论和应用， 可查阅文献［11-12］。

反对称分割指数作为新提出的拓扑指数， 还有很大的发展空间。本文使用冠积G_{\mathrm{1}}\circ G_{\mathrm{2}}、 笛卡尔积G_{\mathrm{1}}\times G_{\mathrm{2}}、 字典序积G_{\mathrm{1}}\left[G_{\mathrm{2}}\right]等图运算， 给出两个反对称分割指数运算后新图的上界， 并刻画了相应的极图。研究图运算下的反对称分割指数有助于理解和应用图的结构性质， 对图运算下的其它有关顶点度的拓扑指数研究具有一定的参考价值。

1 预备知识

定义 1^［13］　Gutman等定义了第一和第二Zagreb指数， 分别为M_{\mathrm{1}}\left(G\right)=\sum _{uv\in E(G)}\left(d_G\left(u\right)+d_G\left(v\right)\right)，M_{\mathrm{2}}\left(G\right)=\sum _{uv\in E\left(G\right)}{d}_G\left(u\right)d_G\left(v\right)。

定义 2^［14］　设图G_{\mathrm{1}}和G_{\mathrm{2}}具有不相交顶点集V\left(G_{\mathrm{1}}\right)和V\left(G_{\mathrm{2}}\right)。定义顶点集为V\left(G_{\mathrm{1}}\right)∪V\left(G_{\mathrm{2}}\right)， 边集为E\left(G_{\mathrm{1}}\right)∪E\left(G_{\mathrm{2}}\right)∪\left\{uv\left|u\in \right.V\left(G_{\mathrm{1}}\right)\right.，\left.v\in V\left(G_{\mathrm{2}}\right)\right\}的图， 即将一个图的每个顶点连接到另一个图的每个顶点， 同时保留两个图原来的所有边， 所得图称为G_{\mathrm{1}}和G_{\mathrm{2}}的联， 记为G_{\mathrm{1}}+G_{\mathrm{2}}。

定义 3^［15］　设图G_{\mathrm{1}}和G_{\mathrm{2}}具有不相交顶点集V\left(G_{\mathrm{1}}\right)和V\left(G_{\mathrm{2}}\right)。定义图G_{\mathrm{1}}和G_{\mathrm{2}}的冠积是通过复制\left|V\left(G_{\mathrm{1}}\right)\right|次G_{\mathrm{2}}， 然后将G_{\mathrm{1}}中顶点v_i和第i个复制的G_{\mathrm{2}}的每一个点连接所得的图集， 记为G_{\mathrm{1}}\circ G_{\mathrm{2}}。其中， \left|V\left(G_{\mathrm{1}}\circ G_{\mathrm{2}}\right)\right|=n_{\mathrm{1}}\left(\mathrm{1}+n_{\mathrm{2}}\right)， \left|E\left(G_{\mathrm{1}}\circ G_{\mathrm{2}}\right)\right|=m_{\mathrm{1}}+n_{\mathrm{1}}\left(n_{\mathrm{2}}+m_{\mathrm{2}}\right)。

定义 4^［16］ 设图G_{\mathrm{1}}和G_{\mathrm{2}}具有不相交顶点集V\left(G_{\mathrm{1}}\right)， V\left(G_{\mathrm{2}}\right)和不相交边集E\left(G_{\mathrm{1}}\right)， E\left(G_{\mathrm{2}}\right)。定义图G_{\mathrm{1}}和G_{\mathrm{2}}的笛卡尔积为顶点集为V\left(G_{\mathrm{1}}\times G_{\mathrm{2}}\right)=V\left(G_{\mathrm{1}}\right)\times V\left(G_{\mathrm{2}}\right)， 边集为E\left(G_{\mathrm{1}}\times G_{\mathrm{2}}\right)=\left\{\left(u_i,v_j\right)\left(u_k,v_l\right)\left|u_i=u_k,v_j{v}_l\in \right.\right.E\left(G_{\mathrm{2}}\right)或v_j=v_l， \left.u_i{u}_k\in E(G_{\mathrm{1}})\right\}的图， 记为G_{\mathrm{1}}\times G_{\mathrm{2}}。

定义 5^［14］ 设图G_{\mathrm{1}}和G_{\mathrm{2}}具有不相交顶点集V\left(G_{\mathrm{1}}\right)， V\left(G_{\mathrm{2}}\right)和不相交边集E\left(G_{\mathrm{1}}\right)， E\left(G_{\mathrm{2}}\right)。定义图G_{\mathrm{1}}和图G_{\mathrm{2}}的字典序积为顶点集为V\left(G_{\mathrm{1}}\left[G_{\mathrm{2}}\right]\right)=V\left(G_{\mathrm{1}}\right)\times V\left(G_{\mathrm{2}}\right)， 边集为E\left(G_{\mathrm{1}}\left[G_{\mathrm{2}}\right]\right)=\left\{\left(u_i,v_j\right)\right.\left.\left(u_k,v_l\right)\right|u_i{u}_k∈E\left(G_{\mathrm{1}}\right)或u_i=\left.u_k,v_j{v}_l\in E\left(G_{\mathrm{2}}\right)\right\}的图， 记为G_{\mathrm{1}}\left[G_{\mathrm{2}}\right]。

定义 6^［17］ 设图G_{\mathrm{1}}和G_{\mathrm{2}}具有不相交顶点集V\left(G_{\mathrm{1}}\right)， V\left(G_{\mathrm{2}}\right)和不相交边集E\left(G_{\mathrm{1}}\right)， E\left(G_{\mathrm{2}}\right)。定义图G_{\mathrm{1}}和图G_{\mathrm{2}}的对称差为顶点集为V\left(G_{\mathrm{1}}\oplus G_{\mathrm{2}}\right)=V\left(G_{\mathrm{1}}\right)\times V\left(G_{\mathrm{2}}\right)， 边集为E\left(G_{\mathrm{1}}\oplus G_{\mathrm{2}}\right)=\left\{\left(u_i,v_j\right)\right.\left(u_k,v_l\right)\left|u_i{u}_k\right.\inE\left(G_{\mathrm{1}}\right)或v_j{v}_l∈E(G_{\mathrm{2}})， 但两者不能同时存在｝的图， 记为G_{\mathrm{1}}\oplus G_{\mathrm{2}}。

2 主要结果

定理 1 设图G_{\mathrm{1}}和G_{\mathrm{2}}是简单连通图， 有\left|V\left(G_{\mathrm{1}}\right)\right|=n_{\mathrm{1}}，\left|V\left(G_{\mathrm{2}}\right)\right|=n_{\mathrm{2}}， \left|E\left(G_{\mathrm{1}}\right)\right|=m_{\mathrm{1}}， \left|E\left(G_{\mathrm{2}}\right)\right|=m_{\mathrm{2}}， 其最大度分别为{\mathrm{\Delta }}_{\mathrm{1}}和{\mathrm{\Delta }}_{\mathrm{2}}， 最小度分别为{\delta }_{\mathrm{1}}和{\delta }_{\mathrm{2}}， 那么

ISDD\left(G_{\mathrm{1}}+G_{\mathrm{2}}\right)\le

\frac{m_{\mathrm{1}}{\left({\mathrm{\Delta }}_{\mathrm{1}}+n_{\mathrm{2}}\right)}^{\mathrm{2}}}{\mathrm{2}{\left({\delta }_{\mathrm{1}}+n_{\mathrm{2}}\right)}^{\mathrm{2}}}+\frac{m_{\mathrm{2}}{\left({\mathrm{\Delta }}_{\mathrm{2}}+n_{\mathrm{1}}\right)}^{\mathrm{2}}}{\mathrm{2}{\left({\delta }_{\mathrm{2}}+n_{\mathrm{1}}\right)}^{\mathrm{2}}}+

\frac{n_{\mathrm{1}}{n}_{\mathrm{2}}\left({\mathrm{\Delta }}_{\mathrm{1}}+n_{\mathrm{2}}\right)\left({\mathrm{\Delta }}_{\mathrm{2}}+n_{\mathrm{1}}\right)}{{\delta }_{\mathrm{1}}^{\mathrm{2}}+{\delta }_{\mathrm{2}}^{\mathrm{2}}+n_{\mathrm{1}}^{\mathrm{2}}+n_{\mathrm{2}}^{\mathrm{2}}+\mathrm{2}{\delta }_{\mathrm{1}}{n}_{\mathrm{2}}+\mathrm{2}{\delta }_{\mathrm{2}}{n}_{\mathrm{1}}}，

等号成立当且仅当G_{\mathrm{1}}和G_{\mathrm{2}}都是正则图。

证明 设V\left(G_{\mathrm{1}}\right)=\left\{u_{\mathrm{1}},u_{\mathrm{2}},\cdots ,u_{n_{\mathrm{1}}}\right\}，V\left(G_{\mathrm{2}}\right)=\left\{v_{\mathrm{1}},v_{\mathrm{2}},\cdots ,v_{n_{\mathrm{2}}}\right\}。由两个图的联定义， 得

d_{G_{\mathrm{1}}+G_{\mathrm{2}}}\left(u\right)=\left\{\begin{array}{c}{d}_{G_{\mathrm{1}}}\left(u\right)+\left|V\left(G_{\mathrm{2}}\right)\right|,\begin{array}{cc}& u\in V\left(G_{\mathrm{1}}\right),\end{array}\\ d_{G_{\mathrm{2}}}\left(u\right)+\left|V\left(G_{\mathrm{1}}\right)\right|,\begin{array}{cc}& u\in V\left(G_{\mathrm{2}}\right),\end{array}\end{array}\right.

其中， u\in V(G_{\mathrm{1}}+G_{\mathrm{2}})。

则

ISDD\left(G_{\mathrm{1}}+G_{\mathrm{2}}\right)=

\sum _{uv\in E\left(G_{\mathrm{1}}+G_{\mathrm{2}}\right)}\frac{d_{G_{\mathrm{1}}+G_{\mathrm{2}}}\left(u\right)d_{G_{\mathrm{1}}+G_{\mathrm{2}}}\left(v\right)}{d_{G_{\mathrm{1}}+G_{\mathrm{2}}}^{\mathrm{2}}\left(u\right)+d_{G_{\mathrm{1}}+G_{\mathrm{2}}}^{\mathrm{2}}\left(v\right)}=

\sum _{uv\in E\left(G_{\mathrm{1}}\right)}\frac{\left(d_{G_{\mathrm{1}}}\left(u\right)+n_{\mathrm{2}}\right)\left(d_{G_{\mathrm{1}}}\left(v\right)+n_{\mathrm{2}}\right)}{{\left(d_{G_{\mathrm{1}}}\left(u\right)+n_{\mathrm{2}}\right)}^{\mathrm{2}}+{\left(d_{G_{\mathrm{1}}}\left(v\right)+n_{\mathrm{2}}\right)}^{\mathrm{2}}}+

\sum _{uv\in E\left(G_{\mathrm{2}}\right)}\frac{\left(d_{G_{\mathrm{2}}}\left(u\right)+n_{\mathrm{1}}\right)\left(d_{G_{\mathrm{2}}}\left(v\right)+n_{\mathrm{1}}\right)}{{\left(d_{G_{\mathrm{2}}}\left(u\right)+n_{\mathrm{1}}\right)}^{\mathrm{2}}+{\left(d_{G_{\mathrm{2}}}\left(v\right)+n_{\mathrm{1}}\right)}^{\mathrm{2}}}+

\sum _{u\in V\left(G_{\mathrm{1}}\right),v\in V\left(G_{\mathrm{2}}\right)}\frac{\left(d_{G_{\mathrm{1}}}\left(u\right)+n_{\mathrm{2}}\right)\left(d_{G_{\mathrm{2}}}\left(v\right)+n_{\mathrm{1}}\right)}{{\left(d_{G_{\mathrm{1}}}\left(u\right)+n_{\mathrm{2}}\right)}^{\mathrm{2}}+{\left(d_{G_{\mathrm{2}}}\left(v\right)+n_{\mathrm{1}}\right)}^{\mathrm{2}}}\le

\sum _{uv\in E\left(G_{\mathrm{1}}\right)}\frac{{\left({\mathrm{\Delta }}_{\mathrm{1}}+n_{\mathrm{2}}\right)}^{\mathrm{2}}}{\mathrm{2}{\left({\delta }_{\mathrm{1}}+n_{\mathrm{2}}\right)}^{\mathrm{2}}}+\sum _{uv\in E\left(G_{\mathrm{2}}\right)}\frac{{\left({\mathrm{\Delta }}_{\mathrm{2}}+n_{\mathrm{1}}\right)}^{\mathrm{2}}}{\mathrm{2}{\left({\delta }_{\mathrm{2}}+n_{\mathrm{1}}\right)}^{\mathrm{2}}}+

\sum _{u\in V\left(G_{\mathrm{1}}\right),v\in V\left(G_{\mathrm{2}}\right)}\frac{\left({\mathrm{\Delta }}_{\mathrm{1}}+n_{\mathrm{2}}\right)\left({\mathrm{\Delta }}_{\mathrm{2}}+n_{\mathrm{1}}\right)}{{\left({\delta }_{\mathrm{1}}+n_{\mathrm{2}}\right)}^{\mathrm{2}}+{\left({\delta }_{\mathrm{2}}+n_{\mathrm{1}}\right)}^{\mathrm{2}}}=

m_{\mathrm{1}}\frac{{\left({\mathrm{\Delta }}_{\mathrm{1}}+n_{\mathrm{2}}\right)}^{\mathrm{2}}}{\mathrm{2}{\left({\delta }_{\mathrm{1}}+n_{\mathrm{2}}\right)}^{\mathrm{2}}}+m_{\mathrm{2}}\frac{{\left({\mathrm{\Delta }}_{\mathrm{2}}+n_{\mathrm{1}}\right)}^{\mathrm{2}}}{\mathrm{2}{\left({\delta }_{\mathrm{2}}+n_{\mathrm{1}}\right)}^{\mathrm{2}}}+

n_{\mathrm{1}}{n}_{\mathrm{2}}\frac{\left({\mathrm{\Delta }}_{\mathrm{1}}+n_{\mathrm{2}}\right)\left({\mathrm{\Delta }}_{\mathrm{2}}+n_{\mathrm{1}}\right)}{{\delta }_{\mathrm{1}}^{\mathrm{2}}+{\delta }_{\mathrm{2}}^{\mathrm{2}}+n_{\mathrm{1}}^{\mathrm{2}}+n_{\mathrm{2}}^{\mathrm{2}}+\mathrm{2}{\delta }_{\mathrm{1}}{n}_{\mathrm{2}}+\mathrm{2}{\delta }_{\mathrm{2}}{n}_{\mathrm{1}}},

等号成立当且仅当d_{G_{\mathrm{1}}}\left(u\right)={\mathrm{\Delta }}_{\mathrm{1}}={\delta }_{\mathrm{1}}，d_{G_{\mathrm{2}}}\left(v\right)={\mathrm{\Delta }}_{\mathrm{2}}={\delta }_{\mathrm{2}}， 其中， u\in V(G_{\mathrm{1}})， v\in V(G_{\mathrm{2}})， 即G_{\mathrm{1}}和G_{\mathrm{2}}都是正则图。

证毕。

定理 2 设图G_{\mathrm{1}}和G_{\mathrm{2}}是简单连通图， 有\left|V\left(G_{\mathrm{1}}\right)\right|=n_{\mathrm{1}}， \left|V\left(G_{\mathrm{2}}\right)\right|=n_{\mathrm{2}}， \left|E\left(G_{\mathrm{1}}\right)\right|=m_{\mathrm{1}}， \left|E\left(G_{\mathrm{2}}\right)\right|=m_{\mathrm{2}}， 其最大度分别为{\mathrm{\Delta }}_{\mathrm{1}}和{\mathrm{\Delta }}_{\mathrm{2}}， 最小度分别为{\delta }_{\mathrm{1}}和{\delta }_{\mathrm{2}}， 那么

ISDD\left(G_{\mathrm{1}}\circ G_{\mathrm{2}}\right)\le

\frac{m_{\mathrm{1}}{\left({\mathrm{\Delta }}_{\mathrm{1}}+n_{\mathrm{2}}\right)}^{\mathrm{2}}}{\mathrm{2}{\left({\delta }_{\mathrm{1}}+n_{\mathrm{2}}\right)}^{\mathrm{2}}}+\frac{n_{\mathrm{1}}{m}_{\mathrm{2}}{\left({\mathrm{\Delta }}_{\mathrm{2}}+\mathrm{1}\right)}^{\mathrm{2}}}{\mathrm{2}{\left({\delta }_{\mathrm{2}}+\mathrm{1}\right)}^{\mathrm{2}}}+

\frac{n_{\mathrm{1}}{n}_{\mathrm{2}}\left({\mathrm{\Delta }}_{\mathrm{1}}+n_{\mathrm{2}}\right)\left({\mathrm{\Delta }}_{\mathrm{2}}+\mathrm{1}\right)}{{\delta }_{\mathrm{1}}^{\mathrm{2}}+{\delta }_{\mathrm{2}}^{\mathrm{2}}+n_{\mathrm{2}}^{\mathrm{2}}+\mathrm{2}{\delta }_{\mathrm{1}}{n}_{\mathrm{2}}+\mathrm{2}{\delta }_{\mathrm{2}}+\mathrm{1}},

等号成立当且仅当G_{\mathrm{1}}和G_{\mathrm{2}}都是正则图。

证明 将G_{\mathrm{1}}\circ G_{\mathrm{2}}的边集分为不相交的三部分， 即E\left(G_{\mathrm{1}}\circ G_{\mathrm{2}}\right)=E_{\mathrm{1}}\bigcup E_{\mathrm{2}}\bigcup E_{\mathrm{3}}， 其中

E_{\mathrm{1}}=\left\{e\in E\left(G_{\mathrm{1}}\circ G_{\mathrm{2}}\right),e\in E\left(G_{\mathrm{1}}\right)\right\}，

E_{\mathrm{2}}=\left\{e\in E\left(G_{\mathrm{1}}\circ G_{\mathrm{2}}\right),e\in E\left(G_{\mathrm{2}}\right)\right\}，

E_{\mathrm{3}}=\left\{e\in E(G_{\mathrm{1}}\circ G_{\mathrm{2}}\right\},

e=uv,\left.u\in V\left(G_{\mathrm{2}}\right),v\in V\left(G_{\mathrm{1}}\right)\right\}\mathrm{。}

由两个图的冠积定义可得

d_{G_{\mathrm{1}}\circ G_{\mathrm{2}}}\left(u\right)=\left\{\begin{array}{c}{d}_{G_{\mathrm{1}}}\left(u\right)+n_{\mathrm{2}},\begin{array}{cc}& u\in V\left(G_{\mathrm{1}}\right);\end{array}\\ d_{G_{\mathrm{2}}}\left(u\right)+\mathrm{1}{,}_{}\begin{array}{cc}& u\in V\left(G_{\mathrm{2}}\right),\end{array}\end{array}\right.

其中， u\in V\left(G_{\mathrm{1}}\circ G_{\mathrm{2}}\right)。

则

ISDD\left(G_{\mathrm{1}}\circ G_{\mathrm{2}}\right)=\sum _{uv\in E\left(G_{\mathrm{1}}\circ G_{\mathrm{2}}\right)}\frac{d_{G_{\mathrm{1}}\circ G_{\mathrm{2}}}\left(u\right)d_{G_{\mathrm{1}}\circ G_{\mathrm{2}}}\left(v\right)}{d_{G_{\mathrm{1}}\circ G_{\mathrm{2}}}^{\mathrm{2}}\left(u\right)+d_{G_{\mathrm{1}}\circ G_{\mathrm{2}}}^{\mathrm{2}}\left(v\right)}=

\sum _{uv\in E_{\mathrm{1}}}\frac{\left(d_{G_{\mathrm{1}}}\left(u\right)+n_{\mathrm{2}}\right)\left(d_{G_{\mathrm{1}}}\left(v\right)+n_{\mathrm{2}}\right)}{{\left(d_{G_{\mathrm{1}}}\left(u\right)+n_{\mathrm{2}}\right)}^{\mathrm{2}}+{\left(d_{G_{\mathrm{1}}}\left(v\right)+n_{\mathrm{2}}\right)}^{\mathrm{2}}}+

n_{\mathrm{1}}\sum _{uv\in E_{\mathrm{2}}}\frac{\left(d_{G_{\mathrm{2}}}\left(u\right)+\mathrm{1}\right)\left(d_{G_{\mathrm{2}}}\left(v\right)+\mathrm{1}\right)}{{\left(d_{G_{\mathrm{2}}}\left(u\right)+\mathrm{1}\right)}^{\mathrm{2}}+{\left(d_{G_{\mathrm{2}}}\left(v\right)+\mathrm{1}\right)}^{\mathrm{2}}}+

\sum _{uv\in E_{\mathrm{3}},u\in V_{\mathrm{1}},v\in V_{\mathrm{2}}}\frac{\left(d_{G_{\mathrm{1}}}\left(u\right)+n_{\mathrm{2}}\right)\left(d_{G_{\mathrm{2}}}\left(v\right)+\mathrm{1}\right)}{{\left(d_{G_{\mathrm{1}}}\left(u\right)+n_{\mathrm{2}}\right)}^{\mathrm{2}}+{\left(d_{G_{\mathrm{2}}}\left(v\right)+\mathrm{1}\right)}^{\mathrm{2}}}\le

\sum _{uv\in E_{\mathrm{1}}}\frac{{\left({\mathrm{\Delta }}_{\mathrm{1}}+n_{\mathrm{2}}\right)}^{\mathrm{2}}}{\mathrm{2}{\left({\delta }_{\mathrm{1}}+n_{\mathrm{2}}\right)}^{\mathrm{2}}}+n_{\mathrm{1}}\sum _{uv\in E_{\mathrm{2}}}\frac{{\left({\mathrm{\Delta }}_{\mathrm{2}}+\mathrm{1}\right)}^{\mathrm{2}}}{\mathrm{2}{\left({\delta }_{\mathrm{2}}+\mathrm{1}\right)}^{\mathrm{2}}}+

\sum _{uv\in E_{\mathrm{3}},u\in V_{\mathrm{1}},v\in V_{\mathrm{2}}}\frac{\left({\mathrm{\Delta }}_{\mathrm{1}}+n_{\mathrm{2}}\right)\left({\mathrm{\Delta }}_{\mathrm{2}}+\mathrm{1}\right)}{{\left({\delta }_{\mathrm{1}}+n_{\mathrm{2}}\right)}^{\mathrm{2}}+{\left({\delta }_{\mathrm{2}}+\mathrm{1}\right)}^{\mathrm{2}}}=

m_{\mathrm{1}}\frac{{\left({\mathrm{\Delta }}_{\mathrm{1}}+n_{\mathrm{2}}\right)}^{\mathrm{2}}}{\mathrm{2}{\left({\delta }_{\mathrm{1}}+n_{\mathrm{2}}\right)}^{\mathrm{2}}}+n_{\mathrm{1}}{m}_{\mathrm{2}}\frac{{\left({\mathrm{\Delta }}_{\mathrm{2}}+\mathrm{1}\right)}^{\mathrm{2}}}{\mathrm{2}{\left({\delta }_{\mathrm{2}}+\mathrm{1}\right)}^{\mathrm{2}}}+

n_{\mathrm{1}}{n}_{\mathrm{2}}\frac{\left({\mathrm{\Delta }}_{\mathrm{1}}+n_{\mathrm{2}}\right)\left({\mathrm{\Delta }}_{\mathrm{2}}+\mathrm{1}\right)}{{\delta }_{\mathrm{1}}^{\mathrm{2}}+{\delta }_{\mathrm{2}}^{\mathrm{2}}+n_{\mathrm{2}}^{\mathrm{2}}+\mathrm{2}{\delta }_{\mathrm{1}}{n}_{\mathrm{2}}+\mathrm{2}{\delta }_{\mathrm{2}}+\mathrm{1}},

等号成立当且仅当d_{G_{\mathrm{1}}}\left(u\right)=d_{G_{\mathrm{1}}}\left(v\right)={\mathrm{\Delta }}_{\mathrm{1}}={\delta }_{\mathrm{1}}， d_{G_{\mathrm{2}}}\left(u\right)=d_{G_{\mathrm{2}}}\left(v\right)={\mathrm{\Delta }}_{\mathrm{2}}={\delta }_{\mathrm{2}}， 即G_{\mathrm{1}}和G_{\mathrm{2}}都是正则图时。

证毕。

定理 3 设图G_{\mathrm{1}}和G_{\mathrm{2}}是简单连通图， 有\left|V\left(G_{\mathrm{1}}\right)\right|=n_{\mathrm{1}}， \left|V\left(G_{\mathrm{2}}\right)\right|=n_{\mathrm{2}}， \left|E\left(G_{\mathrm{1}}\right)\right|=m_{\mathrm{1}}， \left|E\left(G_{\mathrm{2}}\right)\right|=m_{\mathrm{2}}， 其最大度分别为{\mathrm{\Delta }}_{\mathrm{1}}和{\mathrm{\Delta }}_{\mathrm{2}}， 最小度分别为{\delta }_{\mathrm{1}}和{\delta }_{\mathrm{2}}， 那么

ISDD\left(G_{\mathrm{1}}\times G_{\mathrm{2}}\right)\le \left(n_{\mathrm{1}}{m}_{\mathrm{2}}+n_{\mathrm{2}}{m}_{\mathrm{1}}\right)\frac{{\left({\mathrm{\Delta }}_{\mathrm{1}}+{\mathrm{\Delta }}_{\mathrm{2}}\right)}^{\mathrm{2}}}{\mathrm{2}{\left({\delta }_{\mathrm{1}}+{\delta }_{\mathrm{2}}\right)}^{\mathrm{2}}}，

等号成立当且仅当G_{\mathrm{1}}和G_{\mathrm{2}}都是正则图。

证明 设V\left(G_{\mathrm{1}}\right)=\left\{u_{\mathrm{1}},u_{\mathrm{2}},\cdots ,u_{n_{\mathrm{1}}}\right\},V\left(G_{\mathrm{2}}\right)=\left\{v_{\mathrm{1}},v_{\mathrm{2}},\cdots ,v_{n_{\mathrm{2}}}\right\}。由两个图的笛卡尔积定义， 可得

\left|E\left(G_{\mathrm{1}}\times G_{\mathrm{2}}\right)\right|=\left|E\left(G_{\mathrm{1}}\right)\right|\left|V\left(G_{\mathrm{2}}\right)\right|+

\left|E\left(G_{\mathrm{2}}\right)\right|\left|V\left(G_{\mathrm{1}}\right)\right|；

d_{G_{\mathrm{1}}\times G_{\mathrm{2}}}\left(u,v\right)=d_{G_{\mathrm{1}}}\left(u\right)+d_{G_{\mathrm{2}}}\left(v\right)。

则

ISDD\left(G_{\mathrm{1}}\times G_{\mathrm{2}}\right)=\sum _{\left(u_i,v_j\right)\left(u_k,v_l\right)\in E\left(G_{\mathrm{1}}\times G_{\mathrm{2}}\right),\left(u_i,v_j\right)\ne \left(u_k,v_l\right)}\frac{d_{G_{\mathrm{1}}\times G_{\mathrm{2}}}\left(u_i,v_j\right)d_{G_{\mathrm{1}}\times G_{\mathrm{2}}}\left(u_k,v_l\right)}{d_{G_{\mathrm{1}}\times G_{\mathrm{2}}}^{\mathrm{2}}\left(u_i,v_j\right)+d_{G_{\mathrm{1}}\times G_{\mathrm{2}}}^{\mathrm{2}}\left(u_k,v_l\right)}=

\sum _{\left(u_i,v_j\right)\left(u_i,v_l\right)\in E\left(G_{\mathrm{1}}\times G_{\mathrm{2}}\right),v_j{v}_l\in E\left(G_{\mathrm{2}}\right)}\frac{d_{G_{\mathrm{1}}\times G_{\mathrm{2}}}\left(u_i,v_j\right)d_{G_{\mathrm{1}}\times G_{\mathrm{2}}}\left(u_i,v_l\right)}{d_{G_{\mathrm{1}}\times G_{\mathrm{2}}}^{\mathrm{2}}\left(u_i,v_j\right)+d_{G_{\mathrm{1}}\times G_{\mathrm{2}}}^{\mathrm{2}}\left(u_i,v_l\right)}+

\sum _{\left(u_i,v_j\right)\left(u_k,v_j\right)\in E\left(G_{\mathrm{1}}\times G_{\mathrm{2}}\right),u_i{u}_k\in E\left(G_{\mathrm{1}}\right)}\frac{d_{G_{\mathrm{1}}\times G_{\mathrm{2}}}\left(u_i,v_j\right)d_{G_{\mathrm{1}}\times G_{\mathrm{2}}}\left(u_k,v_j\right)}{d_{G_{\mathrm{1}}\times G_{\mathrm{2}}}^{\mathrm{2}}\left(u_i,v_j\right)+d_{G_{\mathrm{1}}\times G_{\mathrm{2}}}^{\mathrm{2}}\left(u_k,v_j\right)}=

\sum _{u_i\in V\left(G_{\mathrm{1}}\right)}\sum _{{}_{}{v}_j{v}_l\in E\left(G_{\mathrm{2}}\right)}\frac{\left(d_{G_{\mathrm{1}}}\left(u_i\right)+d_{G_{\mathrm{2}}}\left(v_j\right)\right)\left(d_{G_{\mathrm{1}}}\left(u_i\right)+d_{G_{\mathrm{2}}}\left(v_l\right)\right)}{{\left(d_{G_{\mathrm{1}}}\left(u_i\right)+d_{G_{\mathrm{2}}}\left(v_j\right)\right)}^{\mathrm{2}}+{\left(d_{G_{\mathrm{1}}}\left(u_i\right)+d_{G_{\mathrm{2}}}\left(v_l\right)\right)}^{\mathrm{2}}}+

\sum _{v_j\in V\left(G_{\mathrm{2}}\right)}\sum _{{}_{}{u}_i{u}_k\in E\left(G_{\mathrm{1}}\right)}\frac{\left(d_{G_{\mathrm{1}}}\left(u_i\right)+d_{G_{\mathrm{2}}}\left(v_j\right)\right)\left(d_{G_{\mathrm{1}}}\left(u_k\right)+d_{G_{\mathrm{2}}}\left(v_j\right)\right)}{{\left(d_{G_{\mathrm{1}}}\left(u_i\right)+d_{G_{\mathrm{2}}}\left(v_j\right)\right)}^{\mathrm{2}}+{\left(d_{G_{\mathrm{1}}}\left(u_k\right)+d_{G_{\mathrm{2}}}\left(v_j\right)\right)}^{\mathrm{2}}}\le

n_{\mathrm{1}}\sum _{v_j{v}_l\in E\left(G_{\mathrm{2}}\right)}\frac{{\left({\mathrm{\Delta }}_{\mathrm{1}}+{\mathrm{\Delta }}_{\mathrm{2}}\right)}^{\mathrm{2}}}{\mathrm{2}{\left({\delta }_{\mathrm{1}}+{\delta }_{\mathrm{2}}\right)}^{\mathrm{2}}}+n_{\mathrm{2}}\sum _{u_i{u}_k\in E\left(G_{\mathrm{1}}\right)}\frac{{\left({\mathrm{\Delta }}_{\mathrm{1}}+{\mathrm{\Delta }}_{\mathrm{2}}\right)}^{\mathrm{2}}}{\mathrm{2}{\left({\delta }_{\mathrm{1}}+{\delta }_{\mathrm{2}}\right)}^{\mathrm{2}}}=

n_{\mathrm{1}}{m}_{\mathrm{2}}\frac{{\left({\mathrm{\Delta }}_{\mathrm{1}}+{\mathrm{\Delta }}_{\mathrm{2}}\right)}^{\mathrm{2}}}{\mathrm{2}{\left({\delta }_{\mathrm{1}}+{\delta }_{\mathrm{2}}\right)}^{\mathrm{2}}}+n_{\mathrm{2}}{m}_{\mathrm{1}}\frac{{\left({\mathrm{\Delta }}_{\mathrm{1}}+{\mathrm{\Delta }}_{\mathrm{2}}\right)}^{\mathrm{2}}}{\mathrm{2}{\left({\delta }_{\mathrm{1}}+{\delta }_{\mathrm{2}}\right)}^{\mathrm{2}}}=

\left(n_{\mathrm{1}}{m}_{\mathrm{2}}+n_{\mathrm{2}}{m}_{\mathrm{1}}\right)\frac{{\left({\mathrm{\Delta }}_{\mathrm{1}}+{\mathrm{\Delta }}_{\mathrm{2}}\right)}^{\mathrm{2}}}{\mathrm{2}{\left({\delta }_{\mathrm{1}}+{\delta }_{\mathrm{2}}\right)}^{\mathrm{2}}},

等号成立当且仅当d_{G_{\mathrm{1}}}\left(u_i\right)=d_{G_{\mathrm{1}}}\left(u_k\right)={\mathrm{\Delta }}_{\mathrm{1}}={\delta }_{\mathrm{1}},d_{G_{\mathrm{2}}}\left(v_j\right)=d_{G_{\mathrm{2}}}\left(v_l\right)={\mathrm{\Delta }}_{\mathrm{2}}={\delta }_{\mathrm{2}}， 其中， u\in V(G_{\mathrm{1}})， v∈V(G_{\mathrm{2}})， 即G_{\mathrm{1}}和G_{\mathrm{2}}都是正则图。

证毕。

定理 4 设图G_{\mathrm{1}}和G_{\mathrm{2}}是简单连通图， 有\left|V\left(G_{\mathrm{1}}\right)\right|=n_{\mathrm{1}}， \left|V\left(G_{\mathrm{2}}\right)\right|=n_{\mathrm{2}}， \left|E\left(G_{\mathrm{1}}\right)\right|=m_{\mathrm{1}}， \left|E\left(G_{\mathrm{2}}\right)\right|=m_{\mathrm{2}}， 其最大度分别为{\mathrm{\Delta }}_{\mathrm{1}}和{\mathrm{\Delta }}_{\mathrm{2}}， 最小度分别为{\delta }_{\mathrm{1}}和{\delta }_{\mathrm{2}}， 那么

ISDD\left(G_{\mathrm{1}}\left[G_{\mathrm{2}}\right]\right)\le

\begin{array}{c}\left(n_{\mathrm{2}}^{\mathrm{2}}{\mathrm{\Delta }}_{\mathrm{1}}^{\mathrm{2}}{m}_{\mathrm{2}}+n_{\mathrm{2}}{\mathrm{\Delta }}_{\mathrm{1}}{M}_{\mathrm{1}}\left(G_{\mathrm{2}}\right)+M_{\mathrm{2}}\left(G_{\mathrm{2}}\right)\right)\frac{n_{\mathrm{1}}}{\mathrm{2}{\left(n_{\mathrm{2}}{\delta }_{\mathrm{1}}+{\delta }_{\mathrm{2}}\right)}^{\mathrm{2}}}+\\ \left(n_{\mathrm{2}}^{\mathrm{2}}{M}_{\mathrm{2}}\left(G_{\mathrm{1}}\right)+n_{\mathrm{2}}{\mathrm{\Delta }}_{\mathrm{2}}{M}_{\mathrm{1}}\left(G_{\mathrm{1}}\right)+{\mathrm{\Delta }}_{\mathrm{2}}^{\mathrm{2}}{m}_{\mathrm{1}}\right)\frac{n_{\mathrm{2}}^{\mathrm{2}}}{\mathrm{2}{\left(n_{\mathrm{2}}{\delta }_{\mathrm{1}}+{\delta }_{\mathrm{2}}\right)}^{\mathrm{2}}},\end{array}

其中，

M_{\mathrm{1}}\left(G_{\mathrm{2}}\right)=\sum _{v_j{v}_l\in E\left(G_{\mathrm{2}}\right)}\left(d_{G_{\mathrm{2}}}\left(v_j\right)+d_{G_{\mathrm{2}}}\left(v_l\right)\right),

M_{\mathrm{2}}\left(G_{\mathrm{2}}\right)=\sum _{v_j{v}_l\in E\left(G_{\mathrm{2}}\right)}{d}_{G_{\mathrm{2}}}\left(v_j\right)d_{G_{\mathrm{2}}}\left(v_l\right)，

M_{\mathrm{2}}\left(G_{\mathrm{1}}\right)=\sum _{u_i{u}_k\in E\left(G_{\mathrm{1}}\right)}{d}_{G_{\mathrm{1}}}\left(u_i\right)d_{G_{\mathrm{1}}}\left(u_k\right),

M_{\mathrm{1}}\left(G_{\mathrm{1}}\right)=\sum _{u_i{u}_k\in E\left(G_{\mathrm{1}}\right)}\left(d_{G_{\mathrm{1}}}\left(u_i\right)+d_{G_{\mathrm{1}}}\left(u_k\right)\right),

等号成立当且仅当G_{\mathrm{1}}和G_{\mathrm{2}}都是正则图。

证明 设V\left(G_{\mathrm{1}}\right)=\left\{u_{\mathrm{1}},u_{\mathrm{2}},\cdots ,u_{n_{\mathrm{1}}}\right\},V\left(G_{\mathrm{2}}\right)=\left\{v_{\mathrm{1}},v_{\mathrm{2}},\cdots ,v_{n_{\mathrm{2}}}\right\}。由两个图的字典序积定义可得

\left|E\left(G_{\mathrm{1}}\left[G_{\mathrm{2}}\right]\right)\right|=\left|E\left(G_{\mathrm{1}}\right)\right|{\left|V\left(G_{\mathrm{2}}\right)\right|}^{\mathrm{2}}+\left|E\left(G_{\mathrm{2}}\right)\right|\left|V\left(G_{\mathrm{1}}\right)\right|，

d_{G_{\mathrm{1}}\left[G_{\mathrm{2}}\right]}\left(u,v\right)=n_{\mathrm{2}}{d}_{G_{\mathrm{1}}}\left(u\right)+d_{G_{\mathrm{2}}}\left(v\right),

则

ISDD\left(G_{\mathrm{1}}\left[G_{\mathrm{2}}\right]\right)=\sum _{\left(u_i,v_j\right)\left(u_k,v_l\right)\in E\left(G_{\mathrm{1}}\left[G_{\mathrm{2}}\right]\right),\left(u_i,v_j\right)\ne \left(u_k,v_l\right)}\frac{d_{G_{\mathrm{1}}\left[G_{\mathrm{2}}\right]}\left(u_i,v_j\right)d_{G_{\mathrm{1}}\left[G_{\mathrm{2}}\right]}\left(u_k,v_l\right)}{d_{G_{\mathrm{1}}\left[G_{\mathrm{2}}\right]}^{\mathrm{2}}\left(u_i,v_j\right)+d_{G_{\mathrm{1}}\left[G_{\mathrm{2}}\right]}^{\mathrm{2}}\left(u_k,v_l\right)}=

\sum _{\left(u_i,v_j\right)\left(u_i,v_l\right)\in E\left(G_{\mathrm{1}}\left[G_{\mathrm{2}}\right]\right),j\ne l}\frac{d_{G_{\mathrm{1}}\left[G_{\mathrm{2}}\right]}\left(u_i,v_j\right)d_{G_{\mathrm{1}}\left[G_{\mathrm{2}}\right]}\left(u_i,v_l\right)}{d_{G_{\mathrm{1}}\left[G_{\mathrm{2}}\right]}^{\mathrm{2}}\left(u_i,v_j\right)+d_{G_{\mathrm{1}}\left[G_{\mathrm{2}}\right]}^{\mathrm{2}}\left(u_i,v_l\right)}+\sum _{\left(u_i,v_j\right)\left(u_k,v_l\right)\in E\left(G_{\mathrm{1}}\left[G_{\mathrm{2}}\right]\right),i\ne k}\frac{d_{G_{\mathrm{1}}\left[G_{\mathrm{2}}\right]}\left(u_i,v_j\right)d_{G_{\mathrm{1}}\left[G_{\mathrm{2}}\right]}\left(u_k,v_l\right)}{d_{G_{\mathrm{1}}\left[G_{\mathrm{2}}\right]}^{\mathrm{2}}\left(u_i,v_j\right)+d_{G_{\mathrm{1}}\left[G_{\mathrm{2}}\right]}^{\mathrm{2}}\left(u_k,v_l\right)}=

\sum _{u_i\in V\left(G_{\mathrm{1}}\right)}\sum _{v_j{v}_l\in E\left(G_{\mathrm{2}}\right)}\frac{\left(n_{\mathrm{2}}{d}_{G_{\mathrm{1}}}\left(u_i\right)+d_{G_{\mathrm{2}}}\left(v_j\right)\right)\left(n_{\mathrm{2}}{d}_{G_{\mathrm{1}}}\left(u_i\right)+d_{G_{\mathrm{2}}}\left(v_l\right)\right)}{{\left(n_{\mathrm{2}}{d}_{G_{\mathrm{1}}}\left(u_i\right)+d_{G_{\mathrm{2}}}\left(v_j\right)\right)}^{\mathrm{2}}+{\left(n_{\mathrm{2}}{d}_{G_{\mathrm{1}}}\left(u_i\right)+d_{G_{\mathrm{2}}}\left(v_l\right)\right)}^{\mathrm{2}}}+

\sum _{u_i{u}_k\in E\left(G_{\mathrm{1}}\right)}\sum _{v_j\in V\left(G_{\mathrm{2}}\right)}\sum _{v_l\in V\left(G_{\mathrm{2}}\right)}\frac{\left(n_{\mathrm{2}}{d}_{G_{\mathrm{1}}}\left(u_i\right)+d_{G_{\mathrm{2}}}\left(v_j\right)\right)\left(n_{\mathrm{2}}{d}_{G_{\mathrm{1}}}\left(u_k\right)+d_{G_{\mathrm{2}}}\left(v_l\right)\right)}{{\left(n_{\mathrm{2}}{d}_{G_{\mathrm{1}}}\left(u_i\right)+d_{G_{\mathrm{2}}}\left(v_j\right)\right)}^{\mathrm{2}}+{\left(n_{\mathrm{2}}{d}_{G_{\mathrm{1}}}\left(u_k\right)+d_{G_{\mathrm{2}}}\left(v_l\right)\right)}^{\mathrm{2}}}=

n_{\mathrm{1}}\sum _{v_j{v}_l\in E\left(G_{\mathrm{2}}\right)}\frac{\left(n_{\mathrm{2}}{d}_{G_{\mathrm{1}}}\left(u_i\right)+d_{G_{\mathrm{2}}}\left(v_j\right)\right)\left(n_{\mathrm{2}}{d}_{G_{\mathrm{1}}}\left(u_i\right)+d_{G_{\mathrm{2}}}\left(v_l\right)\right)}{{\left(n_{\mathrm{2}}{d}_{G_{\mathrm{1}}}\left(u_i\right)+d_{G_{\mathrm{2}}}\left(v_j\right)\right)}^{\mathrm{2}}+{\left(n_{\mathrm{2}}{d}_{G_{\mathrm{1}}}\left(u_i\right)+d_{G_{\mathrm{2}}}\left(v_l\right)\right)}^{\mathrm{2}}}+

n_{\mathrm{2}}^{\mathrm{2}}\sum _{u_i{u}_k\in E\left(G_{\mathrm{1}}\right)}\frac{\left(n_{\mathrm{2}}{d}_{G_{\mathrm{1}}}\left(u_i\right)+d_{G_{\mathrm{2}}}\left(v_j\right)\right)\left(n_{\mathrm{2}}{d}_{G_{\mathrm{1}}}\left(u_k\right)+d_{G_{\mathrm{2}}}\left(v_l\right)\right)}{{\left(n_{\mathrm{2}}{d}_{G_{\mathrm{1}}}\left(u_i\right)+d_{G_{\mathrm{2}}}\left(v_j\right)\right)}^{\mathrm{2}}+{\left(n_{\mathrm{2}}{d}_{G_{\mathrm{1}}}\left(u_k\right)+d_{G_{\mathrm{2}}}\left(v_l\right)\right)}^{\mathrm{2}}}\le n_{\mathrm{1}}\sum _{v_j{v}_l\in E\left(G_{\mathrm{2}}\right)}\frac{\left(n_{\mathrm{2}}{\mathrm{\Delta }}_{\mathrm{1}}+d_{G_{\mathrm{2}}}\left(v_j\right)\right)\left(n_{\mathrm{2}}{\mathrm{\Delta }}_{\mathrm{1}}+d_{G_{\mathrm{2}}}\left(v_l\right)\right)}{\mathrm{2}{\left(n_{\mathrm{2}}{\delta }_{\mathrm{1}}+{\delta }_{\mathrm{2}}\right)}^{\mathrm{2}}}+

n_{\mathrm{2}}^{\mathrm{2}}\sum _{u_i{u}_k\in E\left(G_{\mathrm{1}}\right)}\frac{\left(n_{\mathrm{2}}{d}_{G_{\mathrm{1}}}\left(u_i\right)+{\mathrm{\Delta }}_{\mathrm{2}}\right)\left(n_{\mathrm{2}}{d}_{G_{\mathrm{1}}}\left(u_k\right)+{\mathrm{\Delta }}_{\mathrm{2}}\right)}{\mathrm{2}{\left(n_{\mathrm{2}}{\delta }_{\mathrm{1}}+{\delta }_{\mathrm{2}}\right)}^{\mathrm{2}}}=

\frac{n_{\mathrm{1}}}{\mathrm{2}{\left(n_{\mathrm{2}}{\delta }_{\mathrm{1}}+{\delta }_{\mathrm{2}}\right)}^{\mathrm{2}}}\sum _{v_j{v}_l\in E\left(G_{\mathrm{2}}\right)}\left[n_{\mathrm{2}}^{\mathrm{2}}{\mathrm{\Delta }}_{\mathrm{1}}^{\mathrm{2}}+n_{\mathrm{2}}{\mathrm{\Delta }}_{\mathrm{1}}\left(d_{G_{\mathrm{2}}}\left(v_j\right)+d_{G_{\mathrm{2}}}\left(v_l\right)\right)+d_{G_{\mathrm{2}}}\left(v_j\right)d_{G_{\mathrm{2}}}\left(v_l\right)\right]+

\frac{n_{\mathrm{2}}^{\mathrm{2}}}{\mathrm{2}{\left(n_{\mathrm{2}}{\delta }_{\mathrm{1}}+{\delta }_{\mathrm{2}}\right)}^{\mathrm{2}}}\sum _{u_i{u}_k\in E\left(G_{\mathrm{1}}\right)}\left[n_{\mathrm{2}}^{\mathrm{2}}{d}_{G_{\mathrm{1}}}\left(u_i\right)d_{G_{\mathrm{1}}}\left(u_k\right)+n_{\mathrm{2}}{\mathrm{\Delta }}_{\mathrm{2}}\left(d_{G_{\mathrm{1}}}\left(u_i\right)+d_{G_{\mathrm{1}}}\left(u_k\right)\right)+{\mathrm{\Delta }}_{\mathrm{2}}^{\mathrm{2}}\right]\mathrm{。}（1）

令

M_{\mathrm{1}}\left(G_{\mathrm{2}}\right)=\sum _{v_j{v}_l\in E\left(G_{\mathrm{2}}\right)}\left(d_{G_{\mathrm{2}}}\left(v_j\right)+d_{G_{\mathrm{2}}}\left(v_l\right)\right)，

M_{\mathrm{2}}\left(G_{\mathrm{2}}\right)=\sum _{v_j{v}_l\in E\left(G_{\mathrm{2}}\right)}{d}_{G_{\mathrm{2}}}\left(v_j\right)d_{G_{\mathrm{2}}}\left(v_l\right)；（2）

M_{\mathrm{2}}\left(G_{\mathrm{1}}\right)=\sum _{u_i{u}_k\in E\left(G_{\mathrm{1}}\right)}{d}_{G_{\mathrm{1}}}\left(u_i\right)d_{G_{\mathrm{1}}}\left(u_k\right),

M_{\mathrm{1}}\left(G_{\mathrm{1}}\right)=\sum _{u_i{u}_k\in E\left(G_{\mathrm{1}}\right)}\left(d_{G_{\mathrm{1}}}\left(u_i\right)+d_{G_{\mathrm{1}}}\left(u_k\right)\right)\mathrm{。}（3）

将式（2）和式（3）代入式（1）中， 可得

ISDD\left(G_{\mathrm{1}}\left[G_{\mathrm{2}}\right]\right)\le \frac{n_{\mathrm{1}}}{\mathrm{2}{\left(n_{\mathrm{2}}{\delta }_{\mathrm{1}}+{\delta }_{\mathrm{2}}\right)}^{\mathrm{2}}}\left(n_{\mathrm{2}}^{\mathrm{2}}{\mathrm{\Delta }}_{\mathrm{1}}^{\mathrm{2}}{m}_{\mathrm{2}}+n_{\mathrm{2}}{\mathrm{\Delta }}_{\mathrm{1}}{M}_{\mathrm{1}}\left(G_{\mathrm{2}}\right)+M_{\mathrm{2}}\left(G_{\mathrm{2}}\right)\right)+\frac{n_{\mathrm{2}}^{\mathrm{2}}}{\mathrm{2}{\left(n_{\mathrm{2}}{\delta }_{\mathrm{1}}+{\delta }_{\mathrm{2}}\right)}^{\mathrm{2}}}\left(n_{\mathrm{2}}^{\mathrm{2}}{M}_{\mathrm{2}}\left(G_{\mathrm{1}}\right)+n_{\mathrm{2}}{\mathrm{\Delta }}_{\mathrm{2}}{M}_{\mathrm{1}}\left(G_{\mathrm{1}}\right)+{\mathrm{\Delta }}_{\mathrm{2}}^{\mathrm{2}}{m}_{\mathrm{1}}\right),

等号成立当且仅当d_{G_{\mathrm{1}}}(u_i)=d_{G_{\mathrm{1}}}(u_k)={\mathrm{\Delta }}_{\mathrm{1}}={\delta }_{\mathrm{1}}， d_{G_{\mathrm{2}}}(v_j)=d_{G_{\mathrm{2}}}(v_l)={\mathrm{\Delta }}_{\mathrm{2}}={\delta }_{\mathrm{2}}， 其中， u\in V(G_{\mathrm{1}})， v\in V(G_{\mathrm{2}})， 即G_{\mathrm{1}}和G_{\mathrm{2}}都是正则图。

证毕。

定理 5 设图G_{\mathrm{1}}和G_{\mathrm{2}}是简单连通图， 有\left|V\left(G_{\mathrm{1}}\right)\right|=n_{\mathrm{1}}， \left|V\left(G_{\mathrm{2}}\right)\right|=n_{\mathrm{2}}， \left|E\left(G_{\mathrm{1}}\right)\right|=m_{\mathrm{1}}， \left|E\left(G_{\mathrm{2}}\right)\right|=m_{\mathrm{2}}， 其最大度分别为{\mathrm{\Delta }}_{\mathrm{1}}和{\mathrm{\Delta }}_{\mathrm{2}}， 最小度分别为{\delta }_{\mathrm{1}}和{\delta }_{\mathrm{2}}， 那么

ISDD\left(G_{\mathrm{1}}\oplus G_{\mathrm{2}}\right)\le

\left(n_{\mathrm{2}}^{\mathrm{2}}{m}_{\mathrm{1}}+n_{\mathrm{1}}^{\mathrm{2}}{m}_{\mathrm{2}}-\mathrm{4}{m}_{\mathrm{1}}{m}_{\mathrm{2}}\right)\frac{{\left(n_{\mathrm{2}}{\mathrm{\Delta }}_{\mathrm{1}}+n_{\mathrm{1}}{\mathrm{\Delta }}_{\mathrm{2}}-\mathrm{2}{\delta }_{\mathrm{1}}{\delta }_{\mathrm{2}}\right)}^{\mathrm{2}}}{\mathrm{2}{\left(n_{\mathrm{2}}{\delta }_{\mathrm{1}}+n_{\mathrm{1}}{\delta }_{\mathrm{2}}-\mathrm{2}{\mathrm{\Delta }}_{\mathrm{1}}{\mathrm{\Delta }}_{\mathrm{2}}\right)}^{\mathrm{2}}},

等号成立当且仅当G_{\mathrm{1}}和G_{\mathrm{2}}都是正则图。

证明 设V\left(G_{\mathrm{1}}\right)=\left\{u_{\mathrm{1}},u_{\mathrm{2}},\cdots ,u_{n_{\mathrm{1}}}\right\},V\left(G_{\mathrm{2}}\right)=\left\{v_{\mathrm{1}},v_{\mathrm{2}},\cdots ,v_{n_{\mathrm{2}}}\right\}。由两个图的对称差定义， 得

\left|E\left(G_{\mathrm{1}}\oplus G_{\mathrm{2}}\right)\right|=\left|E\left(G_{\mathrm{1}}\right)\right|{\left|V\left(G_{\mathrm{2}}\right)\right|}^{\mathrm{2}}+

\left|E\left(G_{\mathrm{2}}\right)\right|{\left|V\left(G_{\mathrm{1}}\right)\right|}^{\mathrm{2}}-\mathrm{4}\left|E\left(G_{\mathrm{1}}\right)\right|\left|E\left(G_{\mathrm{2}}\right)\right|,

d_{G_{\mathrm{1}}\oplus G_{\mathrm{2}}}\left(u,v\right)=n_{\mathrm{2}}{d}_{G_{\mathrm{1}}}\left(u\right)+n_{\mathrm{1}}{d}_{G_{\mathrm{2}}}\left(v\right)-

\mathrm{2}{d}_{G_{\mathrm{1}}}\left(u\right)d_{G_{\mathrm{2}}}\left(v\right),

则

ISDD\left(G_{\mathrm{1}}\oplus G_{\mathrm{2}}\right)=\sum _{\left(u_i,v_j\right)\left(u_k,v_l\right)\in E\left(G_{\mathrm{1}}\oplus G_{\mathrm{2}}\right)}\frac{d_{G_{\mathrm{1}}\oplus G_{\mathrm{2}}}\left(u_i,v_j\right)d_{G_{\mathrm{1}}\oplus G_{\mathrm{2}}}\left(u_k,v_l\right)}{d_{G_{\mathrm{1}}\oplus G_{\mathrm{2}}}^{\mathrm{2}}\left(u_i,v_j\right)+d_{G_{\mathrm{1}}\oplus G_{\mathrm{2}}}^{\mathrm{2}}\left(u_k,v_l\right)}=

\sum _{v_j\in V\left(G_{\mathrm{2}}\right)}\sum _{v_l\in V\left(G_{\mathrm{2}}\right)}\sum _{u_i{u}_k\in E\left(G_{\mathrm{1}}\right)}\frac{d_{G_{\mathrm{1}}\oplus G_{\mathrm{2}}}\left(u_i,v_j\right)d_{G_{\mathrm{1}}\oplus G_{\mathrm{2}}}\left(u_k,v_l\right)}{d_{G_{\mathrm{1}}\oplus G_{\mathrm{2}}}^{\mathrm{2}}\left(u_i,v_j\right)+d_{G_{\mathrm{1}}\oplus G_{\mathrm{2}}}^{\mathrm{2}}\left(u_k,v_l\right)}+

\sum _{u_i\in V\left(G_{\mathrm{1}}\right)}\sum _{u_k\in V\left(G_{\mathrm{1}}\right)}\sum _{v_j{v}_l\in E\left(G_{\mathrm{2}}\right)}\frac{d_{G_{\mathrm{1}}\oplus G_{\mathrm{2}}}\left(u_i,v_j\right)d_{G_{\mathrm{1}}\oplus G_{\mathrm{2}}}\left(u_k,v_l\right)}{d_{G_{\mathrm{1}}\oplus G_{\mathrm{2}}}^{\mathrm{2}}\left(u_i,v_j\right)+d_{G_{\mathrm{1}}\oplus G_{\mathrm{2}}}^{\mathrm{2}}\left(u_k,v_l\right)}-

\sum _{u_i{u}_k\in E\left(G_{\mathrm{1}}\right)}\sum _{v_j{v}_l\in E\left(G_{\mathrm{2}}\right)}\frac{d_{G_{\mathrm{1}}\oplus G_{\mathrm{2}}}\left(u_i,v_j\right)d_{G_{\mathrm{1}}\oplus G_{\mathrm{2}}}\left(u_k,v_l\right)}{d_{G_{\mathrm{1}}\oplus G_{\mathrm{2}}}^{\mathrm{2}}\left(u_i,v_j\right)+d_{G_{\mathrm{1}}\oplus G_{\mathrm{2}}}^{\mathrm{2}}\left(u_k,v_l\right)}\mathrm{。}（4）

根据对称差定义， 则

\frac{d_{G_{\mathrm{1}}\oplus G_{\mathrm{2}}}\left(u_i,v_j\right)d_{G_{\mathrm{1}}\oplus G_{\mathrm{2}}}\left(u_k,v_l\right)}{d_{G_{\mathrm{1}}\oplus G_{\mathrm{2}}}^{\mathrm{2}}\left(u_i,v_j\right)+d_{G_{\mathrm{1}}\oplus G_{\mathrm{2}}}^{\mathrm{2}}\left(u_k,v_l\right)}=

\frac{\left(n_{\mathrm{2}}{d}_{G_{\mathrm{1}}}\left(u_i\right)+n_{\mathrm{1}}{d}_{G_{\mathrm{2}}}\left(v_j\right)-\mathrm{2}{d}_{G_{\mathrm{1}}}\left(u_i\right)d_{G_{\mathrm{2}}}\left(v_j\right)\right)\left(n_{\mathrm{2}}{d}_{G_{\mathrm{1}}}\left(u_k\right)+n_{\mathrm{1}}{d}_{G_{\mathrm{2}}}\left(v_l\right)-\mathrm{2}{d}_{G_{\mathrm{1}}}\left(u_k\right)d_{G_{\mathrm{2}}}\left(v_l\right)\right)}{{\left(n_{\mathrm{2}}{d}_{G_{\mathrm{1}}}\left(u_i\right)+n_{\mathrm{1}}{d}_{G_{\mathrm{2}}}\left(v_j\right)-\mathrm{2}{d}_{G_{\mathrm{1}}}\left(u_i\right)d_{G_{\mathrm{2}}}\left(v_j\right)\right)}^{\mathrm{2}}+{\left(n_{\mathrm{2}}{d}_{G_{\mathrm{1}}}\left(u_k\right)+n_{\mathrm{1}}{d}_{G_{\mathrm{2}}}\left(v_l\right)-\mathrm{2}{d}_{G_{\mathrm{1}}}\left(u_k\right)d_{G_{\mathrm{2}}}\left(v_l\right)\right)}^{\mathrm{2}}}\le\frac{{\left(n_{\mathrm{2}}{\mathrm{\Delta }}_{\mathrm{1}}+n_{\mathrm{1}}{\mathrm{\Delta }}_{\mathrm{2}}-\mathrm{2}{\delta }_{\mathrm{1}}{\delta }_{\mathrm{2}}\right)}^{\mathrm{2}}}{\mathrm{2}{\left(n_{\mathrm{2}}{\delta }_{\mathrm{1}}+n_{\mathrm{1}}{\delta }_{\mathrm{2}}-\mathrm{2}{\mathrm{\Delta }}_{\mathrm{1}}{\mathrm{\Delta }}_{\mathrm{2}}\right)}^{\mathrm{2}}}，（5）

将式（5）代入式（4）中得到

ISDD\left(G_{\mathrm{1}}\oplus G_{\mathrm{2}}\right)\le n_{\mathrm{2}}^{\mathrm{2}}{m}_{\mathrm{1}}\frac{{\left(n_{\mathrm{2}}{\mathrm{\Delta }}_{\mathrm{1}}+n_{\mathrm{1}}{\mathrm{\Delta }}_{\mathrm{2}}-\mathrm{2}{\delta }_{\mathrm{1}}{\delta }_{\mathrm{2}}\right)}^{\mathrm{2}}}{\mathrm{2}{\left(n_{\mathrm{2}}{\delta }_{\mathrm{1}}+n_{\mathrm{1}}{\delta }_{\mathrm{2}}-\mathrm{2}{\mathrm{\Delta }}_{\mathrm{1}}{\mathrm{\Delta }}_{\mathrm{2}}\right)}^{\mathrm{2}}}+n_{\mathrm{1}}^{\mathrm{2}}{m}_{\mathrm{2}}\frac{{\left(n_{\mathrm{2}}{\mathrm{\Delta }}_{\mathrm{1}}+n_{\mathrm{1}}{\mathrm{\Delta }}_{\mathrm{2}}-\mathrm{2}{\delta }_{\mathrm{1}}{\delta }_{\mathrm{2}}\right)}^{\mathrm{2}}}{\mathrm{2}{\left(n_{\mathrm{2}}{\delta }_{\mathrm{1}}+n_{\mathrm{1}}{\delta }_{\mathrm{2}}-\mathrm{2}{\mathrm{\Delta }}_{\mathrm{1}}{\mathrm{\Delta }}_{\mathrm{2}}\right)}^{\mathrm{2}}}-

\mathrm{4}{m}_{\mathrm{1}}{m}_{\mathrm{2}}\frac{{\left(n_{\mathrm{2}}{\mathrm{\Delta }}_{\mathrm{1}}+n_{\mathrm{1}}{\mathrm{\Delta }}_{\mathrm{2}}-\mathrm{2}{\delta }_{\mathrm{1}}{\delta }_{\mathrm{2}}\right)}^{\mathrm{2}}}{\mathrm{2}{\left(n_{\mathrm{2}}{\delta }_{\mathrm{1}}+n_{\mathrm{1}}{\delta }_{\mathrm{2}}-\mathrm{2}{\mathrm{\Delta }}_{\mathrm{1}}{\mathrm{\Delta }}_{\mathrm{2}}\right)}^{\mathrm{2}}}=\left(n_{\mathrm{2}}^{\mathrm{2}}{m}_{\mathrm{1}}+n_{\mathrm{1}}^{\mathrm{2}}{m}_{\mathrm{2}}-\mathrm{4}{m}_{\mathrm{1}}{m}_{\mathrm{2}}\right)\frac{{\left(n_{\mathrm{2}}{\mathrm{\Delta }}_{\mathrm{1}}+n_{\mathrm{1}}{\mathrm{\Delta }}_{\mathrm{2}}-\mathrm{2}{\delta }_{\mathrm{1}}{\delta }_{\mathrm{2}}\right)}^{\mathrm{2}}}{\mathrm{2}{\left(n_{\mathrm{2}}{\delta }_{\mathrm{1}}+n_{\mathrm{1}}{\delta }_{\mathrm{2}}-\mathrm{2}{\mathrm{\Delta }}_{\mathrm{1}}{\mathrm{\Delta }}_{\mathrm{2}}\right)}^{\mathrm{2}}},

等号成立当且仅当d_{G_{\mathrm{1}}}(u_i)=d_{G_{\mathrm{1}}}(u_k)={\mathrm{\Delta }}_{\mathrm{1}}={\delta }_{\mathrm{1}}， d_{G_{\mathrm{2}}}(v_j)=d_{G_{\mathrm{2}}}(v_l)={\mathrm{\Delta }}_{\mathrm{2}}={\delta }_{\mathrm{2}}， 其中， u\in V(G_{\mathrm{1}})， v\in V(G_{\mathrm{2}})， 即G_{\mathrm{1}}和G_{\mathrm{2}}都是正则图。

证毕。

3 结论与展望

本文根据反对称分割指数的定义， 给出了G_{\mathrm{1}}+G_{\mathrm{2}}、 G_{\mathrm{1}}\circ G_{\mathrm{2}}、 G_{\mathrm{1}}\times G_{\mathrm{2}}、 G_{\mathrm{1}}\left[G_{\mathrm{2}}\right]和G_{\mathrm{1}}\oplus G_{\mathrm{2}}图运算后的新图上界， 以及达到上界时所需的条件。此研究结果可作为一种预测方法， 对图运算下的其它有关顶点度的拓扑指数的研究有一定的借鉴意义， 后续可以研究其它指数的图运算， 也可发掘更多图运算的计算方法， 进一步丰富图运算的相关内容。

参考文献

[1] BONDY J A， MURTY U S R. Graph theory with applications［M］. London： Macmillan， 1976.

[2] VUKIČEVIĆ D. Bond Additive Modeling 2. Mathematical properties of max-min rodeg index［J］. Croatica Chemica Acta， 2010， 83（3）： 261-273.

[3] DAS K C， MATEJIĆ M， MILOVANOVIĆ E， et al. Bounds for symmetric division deg index of graphs［J］. Filomat， 2019， 33（3）： 683-698.

[4] PALACIOS J L. New upper bounds for the symmetric division deg index of graphs［J］. Discrete Mathematics Letters， 2019（2）： 52-56.

[5] ALI A， ELUMALAI S， MANSOUR T. On the symmetric division deg index of molecular graphs［J］. MATCH Communications in Mathematical and in Computer Chemistry， 2020， 83（1）： 205-220.

[6] GHORBANI M， ZANGI S， AMRAEI N. New results on symmetric division deg index［J］. Journal of Applied Mathematics and Computing， 2021， 65（1）： 161-176.

[7] ALBALAHI A M， ALI A. On the inverse symmetric division deg index of unicyclic graphs［J］. Computation， 2022， 10（10）： 181.

[8] DE N， NAYEEM S M A， PAL A. F-Index of some graph operations［J］. Discrete Mathematics， Algorithms and Applications， 2016， 8（2）： 1650025.

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

[10] IMRAN M， AKHTER S， IQBAL Z. Edge Mostar index of chemical structures and nanostructures using graph operations［J］. International Journal of Quantum Chemistry， 2020， 120（15）： e26259.

[11] MODABISH A， ALAMERI A， GUMAAN M S， et al. The second Hyper-Zagreb index of graph operations［J］. Journal of Mathematics and Computer Science， 2021， 11（2）： 1455-1469.

[12] WANG YING， HAFEEZ S， AKHTER S， et al. The generalized inverse sum indeg index of some graph operations［J］. Symmetry， 2022， 14（11）： 2349.

[13] GUTMAN I， TRINAJSTIĆ N. Graph theory and molecular orbitals. Total φ-electron energy of alternant hydrocarbons［J］. Chemical Physics Letters， 1972， 17（4）： 535-538.

[14] SHETTY B S， LOKESHA V， RANJINI P S. On the Harmonic index of graph operations［J］. Transactions on Combinatorics， 2015， 4（4）： 5-14.

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

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

[17] 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.

基金资助

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

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

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

山西省自然科学基金项目(202303021211154)