Szeged Index and Revised Szeged Index of Two Types of Special Graphs

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

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

对于e=uv∈E(G)，定义如下的集合：

对于e，{N_u(e|G)，N_v(e|G)，N₀(e|G)}是图G的顶点集的划分.令集合N_u(e|G)，N_v(e|G)，N₀(e|G)所包含元素的个数分别为n_u(e|G)，n_v(e|G)，n₀(e|G)，显然有

其中n是图G的顶点数.如果G是二部图，则对∀e∈E(G)，有n₀(e|G)=0，即

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

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

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

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

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

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

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

图G和图H的联图G∨H是一个简单图，其中

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

引理1   $\sum\limits_{e = uv \in E\left( G \right)} $(d_G²(u)+d_G²(v))=M₁³(G).

证  对∀e=uv∈E(G)，d_G²(u)与d_G²(v)均要进行一次求和.换句话说，对∀u∈V(G)，需对d_G²(u)进行d_G(u)次求和.也就是说对∀u∈V(G)，对d_G³(u)进行求和即可得到所求的量.

令t_e(G)表示G中包含边e的三角形的个数，有如下的定理：

定理1  设G是阶数为n₁，边数为m₁的图；H是阶数为n₂，边数为m₂的图.则

其中

证  根据联图的定义，可将G∨H的边集分为3个部分：E(G)，E(H)，E^′={uv：u∈V(G)，v∈V(H)}.

步骤1  对∀e=uv∈E(G)，由于H中的任何顶点与u，v两点均相邻，故对∀w∈V(H)，有d_G∨H(w，u)=d_G∨H(w，v)=1.由联图的定义可知，对∀s∈V(G)，若d_G(s，u)≥2且d_G(s，v)≥2，则

因此

结合引理1，容易得到

步骤2  由联图的定义知G∨H=H∨G，与步骤1讨论类似，有

步骤3  任取e=uv∈E^′={uv：u∈V(G)，v∈V(H)}.对∀s∈V(G)，有d_G∨H(s，v)≤d_G∨H(s，u).而对∀t∈V(H)，若d_H(t，v)≥2，则

因此

结合引理1，容易得到

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

推论1  令图G的阶数为n₁，边数为m₁，且不含三角形；图H的阶数为n₂，边数为m₂，且不含三角形.则

例1  运用联图的定义可以发现S_n=K₁∨ $\overline {{K_n}_{ - 1}} $，K_m，n= $\overline {{K_m}} $∨ $\overline {{K_n}} $，W_n=K₁∨C_n-1，还有K₄=K₂∨K₂.这些特殊图的Szeged指标和修正Szeged指标为

定理2   设G是阶数为n₁，边数为m₁的连通图；H是阶数为n₂，边数为m₂的图.则

其中

证  根据冠图的定义，可将G∘H的边集分为3个部分：E(G)，E(H_i)，E^′={u_iv_ij：u_i∈V(G)，v_ij∈V(H_i)}，其中H_i是H的复制(i=1，2，…，n₁；j=1，2，…，n₂).接下来将对E(G)，E(H_i)，E^′这3个部分里的边进行讨论.

步骤1  对∀e=uv∈E(G)，由于与u对应的H(记作H_u)的所有顶点均与u相邻，且与G中其它顶点均不相邻，故对∀w∈V(H_u)，均有d_G∘H(w，u)=1＜d_G∘H(w，v)=2.类似地，此结论对H_v也成立.此外，对∀s∈V(G)，若d_G(s，u)＜d_G(s，v)，则有d_G∘H(s，u)＜d_G∘H(s，v)成立.进一步可得到：对∀t∈V(H_s)，一定有d_G∘H(t，u)＜d_G∘H(t，v)成立.则

因此

步骤2  任取e=uv∈E(H_i)(i=1，2，…，n₁)，首先对H_i所对应的G中的顶点u_i，有d_G∘H(u_i，u)=d_G∘H(u_i，v)=1.因此根据冠图的定义知：对∀w∉V(H_i)，有d_G∘H(w，u)=d_G∘H(w，v).其次，对∀s∈V(H_i)，当d_Hi(s，u)≥2且d_Hi(s，u)≥2时，有

则

因此

步骤3  任取e=u_iv_ij∈E^′={u_iv_ij：u_i∈V(G)，v_ij∈V(H_i)；i=1，2，…，n₁；j=1，2，…，n₂}，通过之前的讨论，对∀w∉V(H_i)，有d_G∘H(w，u_i)＜d_G∘H(w，v_ij).对∀s∈V(H_i)，若d_Hi(s，v_ij)≥2，则d_G∘H(s，u_i)＜d_G∘H(s，v_ij).而对∀s∈V(H_i)，若d_Hi(s，v_ij)=1，则d_G∘H(s，v_ij)=d_G∘H(s，u_i)=1.则

因此

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

推论2  令连通图G的阶数为n₁，边数为m₁；图H的阶数为n₂，边数为m₂，且不含三角形.则

例2  运用冠图的定义可以发现S_n=K₁∘$\overline {{K_{n - 1}}} $，W_n=K₁∘C_n-1.这些特殊图的Szeged指标和修正Szeged指标为