西南大学学报 (自然科学版)  2020, Vol. 42 Issue (2): 29-35.  DOI: 10.13718/j.cnki.xdzk.2020.02.005
0
Article Options
  • PDF
  • Abstract
  • Figures
  • References
  • 扩展功能
    Email Alert
    RSS
    本文作者相关文章
    杨笑蕊
    强会英
    纳仁花
    李雨虹
    欢迎关注西南大学期刊社
     

  • 两类特殊图的Szeged指标和修正Szeged指标    [PDF全文]
    杨笑蕊1, 强会英1, 纳仁花2, 李雨虹1    
    1. 兰州交通大学 数理学院, 兰州 730070;
    2. 兰州工业学院 基础学科部, 兰州 730050
    摘要:通过对联图和冠图的结构进行分析,得到了这两类运算图的Szeged指标和修正Szeged指标.运用此结论,计算出星图、轮图、完全图以及完全二部图的Szeged指标和修正Szeged指标.
    关键词联图    冠图    Szeged指标    修正Szeged指标    

    本文考虑的所有图均为有限简单图.令G表示顶点集为V(G),边集为E(G)的连通图.对于uvV(G),令dG(uv)表示在图Guv之间的距离.一个连通图G的Wiener指标W(G)是指G中所有顶点对的距离之和,即

    $ W\left( G \right) = \sum\limits_{\left\{ {u, v} \right\} \subseteq V\left( G \right)} {{d_G}\left( {u, v} \right)} $

    Wiener指标是著名化学家H. Wiener在1947年研究烷烃化合物的沸点时提出来的[1].自那之后,Wiener指标被用来解释分子的各种物理化学性质以及与分子结构相关的生物活性.因此,Wiener指标得到了许多数学家和化学家的关注和研究[2-3].

    对于e=uvE(G),定义如下的集合:

    $ {N_u}\left( {e\left| G \right.} \right) = \left\{ {w \in V\left( G \right):{d_G}\left( {u, w} \right) < {d_G}\left( {v, w} \right)} \right\} $
    $ {N_v}\left( {e\left| G \right.} \right) = \left\{ {w \in V\left( G \right):{d_G}\left( {v, w} \right) < {d_G}\left( {u, w} \right)} \right\} $
    $ {N_0}\left( {e\left| G \right.} \right) = \left\{ {w \in V\left( G \right):{d_G}\left( {u, w} \right) = {d_G}\left( {v, w} \right)} \right\} $

    对于e,{Nu(e|G),Nv(e|G),N0(e|G)}是图G的顶点集的划分.令集合Nu(e|G),Nv(e|G),N0(e|G)所包含元素的个数分别为nu(e|G),nv(e|G),n0(e|G),显然有

    $ {n_u}\left( {e\left| G \right.} \right) + {n_v}\left( {e\left| G \right.} \right) + {n_0}\left( {e\left| G \right.} \right) = n $

    其中n是图G的顶点数.如果G是二部图,则对∀eE(G),有n0(e|G)=0,即

    $ {n_u}\left( {e\left| G \right.} \right) + {n_v}\left( {e\left| G \right.} \right) = n $

    当图是一棵树T时,Wiener指标的另一种广泛应用的形式为[4]

    $ W\left( T \right) = \sum\limits_{e = uv \in E\left( T \right)} {{n_u}\left( {e\left| G \right.} \right){n_v}\left( {e\left| G \right.} \right)} $

    基于上述结论,Gutman引入了一个一般图的不变量,并命名为Szeged指标Sz(G)[5]

    $ Sz\left( G \right) = \sum\limits_{e = uv \in E\left( G \right)} {{n_u}\left( {e\left| G \right.} \right){n_v}\left( {e\left| G \right.} \right)} $

    Randić观察到Szeged指标没有考虑到一条边上两个端点距离相等的点,因此他提出了修正Szeged指标的概念[6].图的修正Szeged指标定义为

    $ S{z^ * }\left( G \right) = \sum\limits_{e = uv \in E\left( G \right)} {\left( {{n_u}\left( {e\left| G \right.} \right) + \frac{{{n_0}\left( {e\left| G \right.} \right)}}{2}} \right)\left( {{n_v}\left( {e\left| G \right.} \right) + \frac{{{n_0}\left( {e\left| G \right.} \right)}}{2}} \right)} $

    关于Szeged指标和修正Szeged指标的性质及应用可以参见文献[7-8].

    dG(v)表示在图Gv点的度.为了检测分子的能量,著名数学家、化学家Gutman和Trinájstic在1972年提出第一、第二Zagreb指标的概念[9].图G的第二Zagreb指标M2(G)定义为

    $ {M_2}\left( G \right) = \sum\limits_{uv \in E\left( G \right)} {{d_G}} \left( u \right){d_G}\left( v \right) $

    文献[10]引入了第一广义Zagreb指标的概念

    $ M_1^\alpha \left( G \right) = \sum\limits_{u \in V\left( G \right)} {d_G^\alpha \left( u \right)} $

    其中α为除0和1之外的任意实数.有关Zagreb指标的性质和发展的相关研究,可参考文献[11-12].其它用到的相关定义可参考文献[13].

    G和图H的联图GH是一个简单图,其中

    $ V\left( {G \vee H} \right) = V\left( G \right) \cup V\left( H \right) $
    $ E\left( {G \vee H} \right) = E\left( G \right) \cup E\left( H \right) \cup \left\{ {uv:u \in V\left( G \right), v \in V\left( H \right)} \right\} $

    G和图H的冠图G$ \circ $H是复制1个G和|V(G)|个H,将G中第i个点和第iH中的每个点相连接所得的图,其中1≤i≤|V(G)|.文献[14]给出了笛卡尔积图的Szeged指标.文献[15]得到了笛卡尔积图的修正Szeged指标.有关其它特殊图的研究可参考文献[16].本文得到了联图和冠图的Szeged指标以及修正Szeged指标.运用此结论,可计算出一些特殊图如星图、轮图、完全图和完全二部图的Szeged指标和修正Szeged指标.

    引理1   $\sum\limits_{e = uv \in E\left( G \right)} $(dG2(u)+dG2(v))=M13(G).

      对∀e=uvE(G),dG2(u)与dG2(v)均要进行一次求和.换句话说,对∀uV(G),需对dG2(u)进行dG(u)次求和.也就是说对∀uV(G),对dG3(u)进行求和即可得到所求的量.

    te(G)表示G中包含边e的三角形的个数,有如下的定理:

    定理1  设G是阶数为n1,边数为m1的图;H是阶数为n2,边数为m2的图.则

    $ Sz\left( {G \vee H} \right) = n_1^2n_2^2 - 2n_1^2{m_2} - 2n_2^2{m_1} + 4{m_1}{m_2} + {M_2}\left( G \right) + {M_2}\left( H \right) + \tau \left( G \right) + \tau \left( H \right) $
    $ \begin{array}{l} S{z^ * }\left( {G \vee H} \right) = n_1^2n_2^2 + \frac{1}{4}n_1^2\left( {{m_1} - 3{m_2}} \right) + \frac{1}{4}n_2^2\left( {{m_2} - 3{m_1}} \right) + \\ \;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\frac{3}{2}{n_1}{n_2}\left( {{m_1} + {m_2}} \right) + 2{m_1}{m_2} + \frac{1}{2}\left( {{M_2}\left( G \right) + {M_2}\left( H \right)} \right) - \\ \;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\frac{1}{4}\left( {{n_2}M_1^2\left( G \right) + {n_1}M_1^2\left( H \right)} \right) - \frac{1}{4}\left( {M_1^3\left( G \right) + M_1^3\left( H \right)} \right) \end{array} $

    其中

    $ \tau \left( G \right) = \sum\limits_{e = uv \in E\left( G \right)} {{t_e}} \left( G \right)\left( {{t_e}\left( G \right) - {d_G}\left( u \right) - {d_G}\left( v \right)} \right) $

      根据联图的定义,可将GH的边集分为3个部分:E(G),E(H),E={uvuV(G),vV(H)}.

    步骤1  对∀e=uvE(G),由于H中的任何顶点与uv两点均相邻,故对∀wV(H),有dGH(wu)=dGH(wv)=1.由联图的定义可知,对∀sV(G),若dG(su)≥2且dG(sv)≥2,则

    $ {d_{G \vee H}}\left( {s, u} \right) = {d_{G \vee H}}\left( {s, v} \right) = 2 $

    因此

    $ {n_u}\left( {e\left| {G \vee H} \right.} \right) = {d_G}\left( u \right) - {t_e}\left( G \right) $
    $ {n_v}\left( {e\left| {G \vee H} \right.} \right) = {d_G}\left( v \right) - {t_e}\left( G \right) $
    $ {n_v}\left( {e\left| {G \vee H} \right.} \right) = {n_1} + {n_2} - \left( {{d_G}\left( u \right) + {d_G}\left( v \right) - 2{t_e}\left( G \right)} \right) $

    结合引理1,容易得到

    $ \begin{array}{l} \sum\limits_{e = uv \in E\left( G \right)} {{n_u}\left( {e\left| {G \vee H} \right.} \right){n_v}\left( {e\left| {G \vee H} \right.} \right)} = \\ \sum\limits_{e = uv \in E\left( G \right)} {{d_G}} \left( u \right){d_G}\left( v \right) + \sum\limits_{e = uv \in E\left( G \right)} {\left( {t_e^2\left( G \right) - {t_e}\left( G \right) \cdot \left( {{d_G}\left( u \right) + {d_G}\left( v \right)} \right)} \right)} = {M_2}\left( G \right) + \tau \left( G \right) \end{array} $ (1)
    $ \begin{array}{l} \sum\limits_{e = uv \in E\left( G \right)} {\left[ {{n_u}\left( {e\left| {G \vee H} \right.} \right) + \frac{{{n_0}\left( {e\left| {G \vee H} \right.} \right)}}{2}} \right]} \left( {{n_v}\left( {e\left| {G \vee H} \right.} \right) + \frac{{{n_0}\left( {e\left| {G \vee H} \right.} \right)}}{2}} \right) = \\ \sum\limits_{e = uv \in E\left( G \right)} {\frac{{{n_1} + {n_2} + {d_G}\left( u \right) - {d_G}\left( v \right)}}{2}} \cdot \frac{{{n_1} + {n_2} - {d_G}\left( u \right) + {d_G}\left( v \right)}}{2} = \\ \frac{1}{4}\sum\limits_{e = uv \in E\left( G \right)} {\left( {{{\left( {{n_1} + {n_2}} \right)}^2} - {{\left( {{d_G}\left( u \right) - {d_G}\left( v \right)} \right)}^2}} \right)} = \\ \frac{1}{4}{\left( {{n_1} + {n_2}} \right)^2}{m_1} - \frac{1}{4}\left( {\sum\limits_{u \in V\left( G \right)} {d_G^3} \left( u \right) - 2\sum\limits_{e = uv \in E\left( G \right)} {{d_G}} \left( u \right){d_G}\left( v \right)} \right) = \\ \frac{1}{4}{\left( {{n_1} + {n_2}} \right)^2}{m_1} - \frac{1}{4}M_1^3\left( G \right) + \frac{1}{2}{M_2}\left( G \right) \end{array} $ (2)

    步骤2  由联图的定义知GH=HG,与步骤1讨论类似,有

    $ \sum\limits_{e = uv \in E\left( H \right)} {{n_u}\left( {e\left| {G \vee H} \right.} \right){n_v}\left( {e\left| {G \vee H} \right.} \right)} = {M_2}\left( H \right) + \tau \left( H \right) $ (3)
    $ \begin{array}{l} \sum\limits_{e = uv \in E\left( H \right)} {\left[ {{n_u}\left( {e\left| {G \vee H} \right.} \right) + \frac{{{n_0}\left( {e\left| {G \vee H} \right.} \right)}}{2}} \right]} \left( {{n_v}\left( {e\left| {G \vee H} \right.} \right) + \frac{{{n_0}\left( {e\left| {G \vee H} \right.} \right)}}{2}} \right) = \\ \frac{1}{4}{\left( {{n_1} + {n_2}} \right)^2}{m_2} - \frac{1}{4}M_1^3\left( H \right) + \frac{1}{2}{M_2}\left( H \right) \end{array} $ (4)

    步骤3  任取e=uvE={uvuV(G),vV(H)}.对∀sV(G),有dGH(sv)≤dGH(su).而对∀tV(H),若dH(tv)≥2,则

    $ {d_{G \vee H}}\left( {t, u} \right) = 1 < {d_{G \vee H}}\left( {t, v} \right) = 2 $

    因此

    $ {n_u}\left( {e\left| {G \vee H} \right.} \right) = {n_2} - 1 + 1 - {d_H}\left( v \right) = {n_2} - {d_H}\left( v \right) $
    $ {n_v}\left( {e\left| {G \vee H} \right.} \right) = {n_1} - {d_G}\left( u \right) $
    $ {n_0}\left( {e\left| {G \vee H} \right.} \right) = {d_G}\left( u \right) + {d_H}\left( v \right) $

    结合引理1,容易得到

    $ \begin{array}{l} \sum\limits_{e = uv \in E'} {{n_u}\left( {e\left| {G \vee H} \right.} \right){n_v}\left( {e\left| {G \vee H} \right.} \right)} = \\ \sum\limits_{u \in V\left( G \right)} {\sum\limits_{v \in V\left( H \right)} {\left( {{n_1}{n_2} - {n_1}{d_H}\left( v \right) - {n_2}{d_G}\left( u \right) + {d_G}\left( u \right){d_H}\left( v \right)} \right)} } = \\ n_1^2n_2^2 - 2n_1^2{m_2} - 2n_2^2{m_1} + 4{m_1}{m_2} \end{array} $ (5)
    $ \begin{array}{l} \sum\limits_{e = uv \in E'} {\left( {{n_u}\left( {e\left| {G \vee H} \right.} \right) + \frac{{{n_0}\left( {e\left| {G \vee H} \right.} \right)}}{2}} \right)} \left( {{n_v}\left( {e\left| {G \vee H} \right.} \right) + \frac{{{n_0}\left( {e\left| {G \vee H} \right.} \right)}}{2}} \right) = \\ \sum\limits_{e = uv \in E'} {\left( {{n_2} + \frac{{{d_G}\left( u \right) - {d_H}\left( v \right)}}{2}} \right)} \cdot \left( {{n_1} - \frac{{{d_G}\left( u \right) - {d_H}\left( v \right)}}{2}} \right) = \\ \sum\limits_{u \in V\left( G \right)} {\sum\limits_{v \in V\left( H \right)} {\left( {{n_1}{n_2} + \frac{{\left( {{d_G}\left( u \right) - {d_H}\left( v \right)} \right)\left( {{n_1} - {n_2}} \right)}}{2} - \frac{{{{\left( {{d_G}\left( u \right) - {d_H}\left( v \right)} \right)}^2}}}{4}} \right)} } = \\ n_1^2n_2^2 + \left( {{n_1} - {n_2}} \right)\left( {{n_2}{m_1} - {n_1}{m_2}} \right) + 2{m_1}{m_2} - \frac{1}{4}\left( {{n_2}M_1^2\left( G \right) + {n_1}M_1^2\left( H \right)} \right) \end{array} $ (6)

    综上所述,分别联立(1)(3)(5)式与(2)(4)(6)式,可得

    $ \begin{array}{l} Sz\left( {G \vee H} \right) = {M_2}\left( G \right) + \tau \left( G \right) + {M_2}\left( H \right) + \tau \left( H \right) + n_1^2n_2^2 - 2n_1^2{m_2} - 2n_2^2{m_1} + 4{m_1}{m_2} = \\ \;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;n_1^2n_2^2 - 2n_1^2{m_2} - 2n_2^2{m_1} + 4{m_1}{m_2} + {M_2}\left( G \right) + {M_2}\left( H \right) + \tau \left( G \right) + \tau \left( H \right) \end{array} $
    $ \begin{gathered} S{z^ * }\left( {G \vee H} \right) = \frac{1}{4}{\left( {{n_1} + {n_2}} \right)^2}{m_1} - \frac{1}{4}M_1^3\left( G \right) + \frac{1}{2}{M_2}\left( G \right) + \frac{1}{4}{\left( {{n_1} + {n_2}} \right)^2}{m_2} - \frac{1}{4}M_1^3\left( H \right) + \hfill \\ \;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\frac{1}{2}{M_2}\left( H \right) + n_1^2n_2^2 + \left( {{n_1} - {n_2}} \right)\left( {{n_2}{m_1} - {n_1}{m_2}} \right) + 2{m_1}{m_2} - \frac{1}{4}\left( {{n_2}M_1^2\left( G \right) + {n_1}M_1^2\left( H \right)} \right) = \hfill \\ \;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;n_1^2n_2^2 + \frac{1}{4}n_1^2\left( {{m_1} - 3{m_2}} \right) + \frac{1}{4}n_2^2\left( {{m_2} - 3{m_1}} \right) + \frac{3}{2}{n_1}{n_2}\left( {{m_1} + {m_2}} \right) + 2{m_1}{m_2} + \hfill \\ \;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\frac{1}{2}\left( {{M_2}\left( G \right) + {M_2}\left( H \right)} \right) - \frac{1}{4}\left( {{n_2}M_1^2\left( G \right) + {n_1}M_1^2\left( H \right)} \right) - \frac{1}{4}\left( {M_1^3\left( G \right) + M_1^3\left( H \right)} \right) \hfill \\ \end{gathered} $

    推论1  令图G的阶数为n1,边数为m1,且不含三角形;图H的阶数为n2,边数为m2,且不含三角形.则

    $ Sz\left( {G \vee H} \right) = n_1^2n_2^2 - 2n_1^2{m_2} - 2n_2^2{m_1} + 4{m_1}{m_2} + {M_2}\left( G \right) + {M_2}\left( H \right) $

    例1  运用联图的定义可以发现Sn=K1$\overline {{K_n}_{ - 1}} $Kmn= $\overline {{K_m}} $$\overline {{K_n}} $Wn=K1Cn-1,还有K4=K2K2.这些特殊图的Szeged指标和修正Szeged指标为

    $ Sz\left( {{S_n}} \right) = S{z^ * }\left( {{S_n}} \right) = Sz\left( {{K_1} \vee \overline {{K_{n - 1}}} } \right) = {\left( {n - 1} \right)^2} $
    $ Sz\left( {{K_{m, n}}} \right) = S{z^ * }\left( {{K_{m, n}}} \right) = Sz\left( {\overline {{K_m}} \vee \overline {{K_n}} } \right) = {m^2}{n^2} $
    $ Sz\left( {{W_n}} \right) = Sz\left( {{K_1} \vee {C_{n - 1}}} \right) = {n^2} - 1 $
    $ S{z^ * }\left( {{W_n}} \right) = \mathit{S}{\mathit{z}^ * }\left( {{K_1} \vee {C_{n - 1}}} \right) = \frac{1}{4}{n^2}\left( {n - 1} \right) + 2\left( {n - 1} \right)\left( {n - 2} \right) $
    $ Sz\left( {{K_4}} \right) = Sz\left( {{K_2} \vee {K_2}} \right) = 6 $
    $ S{z^ * }\left( {{K_4}} \right) = S{z^ * }\left( {{K_2} \vee {K_2}} \right) = 24 $

    定理2   设G是阶数为n1,边数为m1的连通图;H是阶数为n2,边数为m2的图.则

    $ Sz\left( {G \circ H} \right) = n_1^2{n_2}\left( {{n_2} + 1} \right) - {n_1}{n_2} - 2{n_1}{m_2} + {\left( {{n_2} + 1} \right)^2}Sz\left( G \right) + {n_1}{M_2}\left( H \right) + {n_1}\tau \left( H \right) $
    $ \begin{array}{l} S{z^ * }\left( {G \circ H} \right) = \frac{1}{4}n_1^3{\left( {{n_2} + 1} \right)^2}{m_2} + n_1^2\left( {{n_2} + 1} \right)\left( {{n_2} + {m_2}} \right) - {n_1}{n_2} - 2{n_1}{m_2} + {\left( {{n_2} + 1} \right)^2}S{z^ * }\left( G \right) + \\ \;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\frac{{{n_1}}}{2}{M_2}\left( H \right) - \frac{{{n_1}}}{4}M_1^2\left( H \right) - \frac{{{n_1}}}{4}M_1^3\left( H \right) \end{array} $

    其中

    $ \tau \left( H \right) = \sum\limits_{e = uv \in E\left( H \right)} {{t_e}} \left( H \right)\left( {{t_e}\left( H \right) - {d_H}\left( u \right) - {d_H}\left( v \right)} \right) $

      根据冠图的定义,可将GH的边集分为3个部分:E(G),E(Hi),E={uivijuiV(G),vijV(Hi)},其中HiH的复制(i=1,2,…,n1j=1,2,…,n2).接下来将对E(G),E(Hi),E这3个部分里的边进行讨论.

    步骤1  对∀e=uvE(G),由于与u对应的H(记作Hu)的所有顶点均与u相邻,且与G中其它顶点均不相邻,故对∀wV(Hu),均有dGH(wu)=1<dGH(wv)=2.类似地,此结论对Hv也成立.此外,对∀sV(G),若dG(su)<dG(sv),则有dGH(su)<dGH(sv)成立.进一步可得到:对∀tV(Hs),一定有dGH(tu)<dGH(tv)成立.则

    $ {n_u}\left( {e\left| {G \circ H} \right.} \right) = {n_u}\left( {e\left| G \right.} \right) + {n_u}\left( {e\left| G \right.} \right){n_2} = {n_u}\left( {e\left| G \right.} \right)\left( {{n_2} + 1} \right) $
    $ {n_v}\left( {e\left| {G \circ H} \right.} \right) = {n_v}\left( {e\left| G \right.} \right)\left( {{n_2} + 1} \right) $
    $ {n_0}\left( {e\left| {G \circ H} \right.} \right) = {n_0}\left( {e\left| G \right.} \right)\left( {{n_2} + 1} \right) $

    因此

    $ \sum\limits_{e = uv \in E\left( G \right)} {{n_u}\left( {e\left| {G \circ H} \right.} \right){n_v}\left( {e\left| {G \circ H} \right.} \right)} = {\left( {{n_2} + 1} \right)^2}\sum\limits_{e = uv \in E\left( G \right)} {{n_u}} \left( {e\left| G \right.} \right){n_v}\left( {e\left| G \right.} \right) = {\left( {{n_2} + 1} \right)^2}Sz\left( G \right) $ (7)
    $ \begin{array}{l} \sum\limits_{e = uv \in E\left( G \right)} {\left( {{n_u}\left( {e\left| {G \circ H} \right.} \right) + \frac{{{n_0}\left( {e\left| {G \circ H} \right.} \right)}}{2}} \right)} \left( {{n_v}\left( {e\left| {G \circ H} \right.} \right) + \frac{{{n_0}\left( {e\left| {G \circ H} \right.} \right)}}{2}} \right) = \\ \sum\limits_{e = uv \in E\left( G \right)} {{{\left( {{n_2} + 1} \right)}^2}} \cdot \left( {{n_u}\left( {e\left| G \right.} \right) + \frac{{{n_0}\left( {e\left| G \right.} \right)}}{2}} \right) \cdot \left( {{n_v}\left( {e\left| G \right.} \right) + \frac{{{n_0}\left( {e\left| G \right.} \right)}}{2}} \right) = \\ {\left( {{n_2} + 1} \right)^2}S{z^ * }\left( G \right) \end{array} $ (8)

    步骤2  任取e=uvE(Hi)(i=1,2,…,n1),首先对Hi所对应的G中的顶点ui,有dGH(uiu)=dGH(uiv)=1.因此根据冠图的定义知:对∀wV(Hi),有dGH(wu)=dGH(wv).其次,对∀sV(Hi),当dHi(su)≥2且dHi(su)≥2时,有

    $ {d_{G \circ H}}\left( {s, u} \right) = {d_{G \circ H}}\left( {s, v} \right) = 2 $

    $ {n_u}\left( {e\left| {G \circ H} \right.} \right) = {d_{{H_i}}}\left( u \right) - {t_e}\left( {{H_i}} \right) $
    $ {n_v}\left( {e\left| {G \circ H} \right.} \right) = {d_{{H_i}}}\left( v \right) - {t_e}\left( {{H_i}} \right) $
    $ {n_0}\left( {e\left| {G \circ H} \right.} \right) = {n_1}\left( {{n_2} + 1} \right) - \left( {{d_{{H_i}}}\left( u \right) + {d_{{H_i}}}\left( v \right) - 2{t_e}\left( {{H_i}} \right)} \right) $

    因此

    $ \begin{array}{l} \sum\limits_{i = 1}^{{n_1}} {\sum\limits_{e = uv \in E\left( {{H_i}} \right)} {{n_u}} } \left( {e\left| {G \circ H} \right.} \right){n_v}\left( {e\left| {G \circ H} \right.} \right) = \\ \sum\limits_{i = 1}^{{n_1}} {\sum\limits_{e = uv \in E\left( {{H_i}} \right)} {{d_{{H_i}}}\left( u \right){d_{{H_i}}}\left( v \right)} } + \sum\limits_{i = 1}^{{n_1}} {\sum\limits_{e = uv \in E\left( {{H_i}} \right)} {{t_e}\left( {{H_i}} \right)} } \cdot \left( {{t_e}\left( {{H_i}} \right) - {d_{{H_i}}}\left( u \right) - {d_{{H_i}}}\left( v \right)} \right) = \\ {n_1}{M_2}\left( H \right) + {n_1}\tau \left( H \right) \end{array} $ (9)
    $ \begin{array}{l} \sum\limits_{i = 1}^{{n_1}} {\sum\limits_{e = uv \in E\left( {{H_i}} \right)} {\left( {{n_u}\left( {e\left| {G \circ H} \right.} \right) + \frac{{{n_0}\left( {e\left| {G \circ H} \right.} \right)}}{2}} \right) \cdot \left( {{n_v}\left( {e\left| {G \circ H} \right.} \right) + \frac{{{n_0}\left( {e\left| {G \circ H} \right.} \right)}}{2}} \right)} } = \\ \sum\limits_{i = 1}^{{n_1}} {\sum\limits_{e = uv \in E\left( {{H_i}} \right)} {\frac{{n_1^2{{\left( {{n_2} + 1} \right)}^2} - {{\left( {{d_{{H_i}}}\left( u \right) - {d_{{H_i}}}\left( v \right)} \right)}^2}}}{4}} } = \\ \frac{{n_1^3{{\left( {{n_2} + 1} \right)}^2}{m_2}}}{4} - \sum\limits_{i = 1}^{{n_1}} {\sum\limits_{e = uv \in E\left( {{H_i}} \right)} {\frac{{d_{{H_i}}^2\left( u \right) + d_{{H_i}}^2\left( v \right) - 2{d_{{H_i}}}\left( u \right){d_{{H_i}}}\left( v \right)}}{4}} } = \\ \frac{1}{4}n_1^3{\left( {{n_2} + 1} \right)^2}{m_2} - \frac{{{n_1}}}{4}M_1^3\left( H \right) + \frac{{{n_1}}}{2}{M_2}\left( H \right) \end{array} $ (10)

    步骤3  任取e=uivijE={uivijuiV(G),vijV(Hi);i=1,2,…,n1j=1,2,…,n2},通过之前的讨论,对∀wV(Hi),有dGH(wui)<dGH(wvij).对∀sV(Hi),若dHi(svij)≥2,则dGH(sui)<dGH(svij).而对∀sV(Hi),若dHi(svij)=1,则dGH(svij)=dGH(sui)=1.则

    $ {n_{{u_i}}}\left( {e\left| {G \circ H} \right.} \right) = {n_1}\left( {{n_2} + 1} \right) - \left( {{d_{{H_i}}}\left( {{v_{ij}}} \right) + 1} \right) $
    $ {n_{{v_{ij}}}}\left( {e\left| {G \circ H} \right.} \right) = 1 $
    $ {n_0}\left( {e\left| {G \circ H} \right.} \right) = {d_{{H_i}}}\left( {{v_{ij}}} \right) $

    因此

    $ \begin{array}{*{20}{c}} {\sum\limits_{e = uv \in E'} {{n_u}} \left( {e\left| {G \circ H} \right.} \right){n_v}\left( {e\left| {G \circ H} \right.} \right) = \sum\limits_{i = 1}^{{n_1}} {\sum\limits_{v \in V\left( {{H_i}} \right)} {\left( {{n_1}\left( {{n_2} + 1} \right) - {d_{{H_i}}}\left( v \right) - 1} \right)} } = }\\ {n_1^2{n_2}\left( {{n_2} + 1} \right) - 2{n_1}{m_2} - {n_1}{n_2}} \end{array} $ (11)
    $ \begin{array}{l} \sum\limits_{e = uv \in E'} {\left( {{n_u}\left( {e\left| {G \circ H} \right.} \right) + \frac{{{n_0}\left( {e\left| {G \circ H} \right.} \right)}}{2}} \right)} \left( {{n_v}\left( {e\left| {G \circ H} \right.} \right) + \frac{{{n_0}\left( {e\left| {G \circ H} \right.} \right)}}{2}} \right) = \\ \sum\limits_{e = uv \in E'} {\left( {\frac{{{n_1}\left( {{n_2} + 1} \right)\left( {{d_{{H_i}}}\left( v \right) + 2} \right)}}{2} - \frac{{{{\left( {{d_{{H_i}}}\left( v \right) + 2} \right)}^2}}}{4}} \right)} = \\ \sum\limits_{i = 1}^{{n_1}} {\sum\limits_{v \in V\left( {{H_i}} \right)} {\left( {{n_1}\left( {{n_2} + 1} \right) + \frac{{{n_1}\left( {{n_2} + 1} \right){d_{{H_i}}}(v)}}{2} - \frac{{d_{{H_i}}^2(v) + 4{d_{{H_i}}}(v) + 4}}{4}} \right)} } = \\ n_1^2{n_2}\left( {{n_2} + 1} \right) + n_1^2\left( {{n_2} + 1} \right){m_2} - \frac{{{n_1}}}{4}M_1^2\left( H \right) - 2{n_1}{m_2} - {n_1}{n_2} \end{array} $ (12)

    综上所述,分别联立(7)(9)(11)式与(8)(10)(12)式,可得

    $ \begin{array}{l} Sz\left( {G \circ H} \right) = {\left( {{n_2} + 1} \right)^2}Sz\left( G \right) + {n_1}{M_2}\left( H \right) + {n_1}\tau \left( H \right) + n_1^2{n_2}\left( {{n_2} + 1} \right) - 2{n_1}{m_2} - {n_1}{n_2} = \\ \;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;n_1^2{n_2}\left( {{n_2} + 1} \right) - {n_1}{n_2} - 2{n_1}{m_2} + {\left( {{n_2} + 1} \right)^2}Sz\left( G \right) + {n_1}{M_2}\left( H \right) + {n_1}\tau \left( H \right) \end{array} $
    $ \begin{array}{l} S{z^ * }\left( {G \vee H} \right) = {\left( {{n_2} + 1} \right)^2}S{z^ * }\left( G \right) + \frac{1}{4}n_1^3{\left( {{n_2} + 1} \right)^2}{m_2} - \frac{{{n_1}}}{4}M_1^3\left( H \right) + \frac{{{n_1}}}{2}{M_2}\left( H \right) + \\ \;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;n_1^2{n_2}\left( {{n_2} + 1} \right) + n_1^2\left( {{n_2} + 1} \right){m_2} - \frac{{{n_1}}}{4}M_1^2\left( H \right) - 2{n_1}{m_2} - {n_1}{n_2} = \\ \;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\frac{1}{4}n_1^3{\left( {{n_2} + 1} \right)^2}{m_2} + n_1^2\left( {{n_2} + 1} \right)\left( {{n_2} + {m_2}} \right) - {n_1}{n_2} - 2{n_1}{m_2} + {\left( {{n_2} + 1} \right)^2}S{z^ * }\left( G \right) + \\ \;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\frac{{{n_1}}}{2}{M_2}\left( H \right) - \frac{{{n_1}}}{4}M_1^2\left( H \right) - \frac{{{n_1}}}{4}M_1^3\left( H \right) \end{array} $

    推论2  令连通图G的阶数为n1,边数为m1;图H的阶数为n2,边数为m2,且不含三角形.则

    $ Sz\left( {G \circ H} \right) = n_1^2{n_2}\left( {{n_2} + 1} \right) - {n_1}{n_2} - 2{n_1}{m_2} + {\left( {{n_2} + 1} \right)^2}Sz\left( G \right) + {n_1}{M_2}\left( H \right) $

    例2  运用冠图的定义可以发现Sn=K1$\overline {{K_{n - 1}}} $Wn=K1Cn-1.这些特殊图的Szeged指标和修正Szeged指标为

    $ Sz\left( {{S_n}} \right) = S{z^ * }\left( {{S_n}} \right) = Sz\left( {{K_1} \circ \overline {{K_{n - 1}}} } \right) = {\left( {n - 1} \right)^2} $
    $ Sz\left( {{W_n}} \right) = Sz\left( {{\mathit{K}_1} \circ {C_{n - 1}}} \right) = {n^2} - 1 $
    $ S{z^ * }\left( {{W_n}} \right) = S{z^ * }\left( {{K_1} \circ {C_{n - 1}}} \right) = \frac{1}{4}{n^2}\left( {n - 1} \right) + 2\left( {n - 1} \right)\left( {n - 2} \right) $
    参考文献
    [1]
    WIENER H. Structural Determination of Paraffin Boiling Points[J]. Journal of the American Chemical Society, 1947, 69(1): 17-20. DOI:10.1021/ja01193a005
    [2]
    CHEN L, LI X L, LIU M M. The (Revised) Szeged Index and the Wiener Index of a Nonbipartite Graph[J]. European Journal of Combinatorics, 2014, 36: 237-246. DOI:10.1016/j.ejc.2013.07.019
    [3]
    GUTMAN I, YEH Y N, LEE S L, et al. Some Recent Results in the Theory of the Wiener Number[J]. Indian Journal of Chemistry, 1993, 32(A): 651-661.
    [4]
    GUTMAN I, POLANSKY O E. Mathematical Concepts in Organic Chemistry[M]. New-York: Springer-Verlag, 1986.
    [5]
    GUTMAN I. A Formula for the Wiener Number of Trees and Its Extension to Graphs Containing Cycles[J]. Graph Theory Notes of New York, 1994, 27: 9-15.
    [6]
    RANDIĆ M. On Generalization of Wiener Index for Cyclic Structures[J]. Acta Chimica Slovenica, 2008, 49(3): 483-496.
    [7]
    JI S J, LIU M M, WU J L. A Lower Bound of Revised Szeged Index of Bicyclic Graphs[J]. Applied Mathematics and Computation, 2018, 316: 480-487. DOI:10.1016/j.amc.2017.08.051
    [8]
    LI X L, LIU M M. Bicyclic Graphs with Maximal Revised Szeged Index[J]. Discrete Applied Mathematics, 2013, 161(16-17): 2527-2531. DOI:10.1016/j.dam.2013.04.002
    [9]
    GUTMAN I, TRINAJSTIĆ N. Graph Theory and Molecular Orbitals. Total Φ-Electron Energy of Alternant Hydrocarbons[J]. Chem Phys Lett, 1972, 17(4): 535-538. DOI:10.1016/0009-2614(72)85099-1
    [10]
    LI X L, ZHENG J. A Unified Approach to the Extremal Trees for Different Indices[J]. Match Communications in Mathematical & in Computer Chemistry, 2005, 54(1): 195-208.
    [11]
    TODESCHINI R, CONSONNI V. Handbook of Molecular Descriptors[M]. Weinheim, Germany: Wiley-VCH Verlag GmbH, 2000.
    [12]
    LIU M H, LIU B L. Some Properties of the First General Zagreb Index[J]. Australas J Combin, 2010, 47: 285-294.
    [13]
    BONDY J A, MURTY U S R. Graph Theory with Applications[M]. London: Macmillan Education UK, 1976.
    [14]
    KLAVŽAR S, RAJAPAKSE A, GUTMAN I. The Szeged and the Wiener Index of Graphs[J]. Applied Mathematics Letters, 1996, 9(5): 45-49. DOI:10.1016/0893-9659(96)00071-7
    [15]
    NAGARAJAN S, PATTABIRAMAN K, CHENDRASEKHARAN M. Revised Szeged Index of Product Graphs[J]. General Mathematics Notes, 2014, 23(2): 71-78.
    [16]
    高炜, 梁立, 徐天伟. 树状纳米星的修改的Szeged指数[J]. 西南大学学报(自然科学版), 2016, 38(11): 95-99.
    Szeged Index and Revised Szeged Index of Two Types of Special Graphs
    YANG Xiao-rui1, QIANG Hui-ying1, NA Ren-hua2, LI Yu-hong1    
    1. School of Mathematics and Science, Lanzhou Jiaotong University, Lanzhou 730070, China;
    2. College of Basic Subject, Lanzhou Institute of Technology, Lanzhou 730050, China
    Abstract: The Szeged index and revised Szeged index of two kinds of operational graphs are obtained by analyzing the structures of the join graph and corona graph. Using these conclusions, the Szeged index and the revised Szeged index of the star graph, wheel graph, complete graph and complete bipartite graph can be computed.
    Key words: join graph    corona graph    Szeged index    revised Szeged index    
    X