一类广义Petersen图的Wiener指标

李伊昊，红 霞

(洛阳师范学院 数学科学学院，河南 洛阳 471022)

0 引 言

本文所指的图均为无向简单图，没有给出说明的符号同文献[1]。设G=(V，E)是有n个顶点的简单连通图，其中V=V(G)和E=E(G)分别为顶点集和边集。对于任意2个顶点u，v∈V(G)，两点间的距离d(u，v)为u和v之间的最短路径长度，记为dG(u，v)。1947年，H.Wiener[2]首次提出了指标的概念。它不仅是图论领域中的重要参数，而且在化学领域中能够准确反映出分子图的特征和性质。基于很多领域内的应用，学者们开始关注Wiener指标，到目前为止研究了很多相关结果。李建喜等[3]给出了单圈图的Wiener指标和外围Wiener指标的计算公式；邵云[4]研究了单圈图的平均Wiener指标。苏晓海[5]研究了单圈图的边平均Wiener指标。吉亚迪[6]等人研究了图Ln的Wiener指数和Gutman指数，这里Ln表示n个六边形和2n个正方形构成的线性结构分子图。李丹怡等[8]考虑了双繁星的Wiener指标的极值问题，本文主要研究一类广义Petersen图的Wiener指标的计算公式。

1 基本概念

定义1[2]Wiener指标为图G中无序点对的距离之和，并记为W(G)，即

W(G)=∑{v，u}⊆V(G)dG(v，u)

定义2[7]设广义Petersen图G=P(n，k)，n≠2k， 是2n个顶点的图，其顶点集和边集分别为

V(G)={u1，u2，…，un，v1，v2，…，vn}
E(G)={vivi+k(mod n)，uivi，uiui+1(mod n)|i=1，2，…，n}

2 主要结果

定理1设G=P(n，2)，n≥5，则

证明设G=P(n，2)，n≥3，图G的顶点集合和边集合如定义2所示。下面分4种情况来讨论G的Wiener指标W(G)。

情况1当n≡0(mod4)且n≥8时，对于给定顶点vi到其它顶点vj(j≠i)的距离有

从而顶点vi到其它顶点vj的距离之和为

再由图G的结构对称性，走遍所有顶点vi(1≤i≤n)，得出任意2个不同顶点之间的距离之和为

对于给定顶点ui到其它顶点uj(j≠i)的距离有

若uj∈{u(i-k)(mod n)，u(i+k)(mod n)}，1≤k≤4，则dG(ui，uj)=k

从而顶点ui到其它顶点uj(j≠i)的距离之和为

再由图G的结构对称性，走遍所有顶点ui(1≤i≤n)，得出任意2个不同顶点之间的距离之和为

对于给定顶点ui到其它顶点vj的距离有

从而顶点ui到其它顶点vj的距离之和为

再由图G的结构对称性，走遍所有顶点ui(1≤i≤n)，得出任意2个不同顶点之间的距离之和为

综上所述，有

W(G)=W1+W2+W3

情况2当n≡1(mod4)时，容易计算，若n=5，则W(G)=75。若n=9，则W(G)=360。

若n≥13，对于给定顶点vi到其它顶点vj(j≠i)的距离有

从而顶点vi到其它顶点vj(j≠i)的距离之和为

再由图G的结构对称性，走遍所有顶点vi(1≤i≤n)，得出任意2个不同顶点之间的距离之和为

对于给定顶点ui到其它顶点ui(j≠i)的距离有

若uj∈{u(i-k)(mod n)，u(i+k)(mod n)}，1≤k≤4，则dG(ui，uj)=k

从而顶点ui到其它顶点uj(j≠i)的距离之和为

再由图G的结构对称性，走遍所有顶点ui(1≤i≤n)， 得出任意2个不同顶点之间的距离之和为

对于给定顶点ui到其它顶点vj的距离有

从而顶点ui到其它顶点vj的距离之和为

再由图G的结构对称性，走遍所有顶点ui(1≤i≤n)， 得出任意2个不同顶点之间的距离之和为

综上所述，有

W(G)=W1+W2+W3

情况3 当n≡2(mod4)时，容易计算，若n=6，则W(G)=135

若n≥10，对于给定顶点vi到其它顶点vj(j≠i)的距离有

从而顶点vi到其它顶点vj(j≠i)的距离之和为

再由图G的结构对称性，走遍所有顶点vi(1≤i≤n)，得出任意2个不同顶点之间的距离之和为

对于给定顶点ui到其它顶点uj(j≠i)的距离有

若uj∈{u(i-k)(mod n)，u(i+k)(mod n)}，1≤k≤4，则dG(ui，uj)=k

从而顶点ui到其它顶点uj(j≠i)的距离之和为

再由图G的结构对称性，走遍所有顶点ui(1≤i≤n)， 得出任意2个不同顶点之间的距离之和为

对于给定顶点ui到其它顶点vj的距离有

从而顶点ui到其它顶点vj的距离之和为

再由图G的结构对称性，走遍所有顶点ui(1≤i≤n)，得出任意2个不同顶点之间的距离之和为

综上所述，有

W(G)=W1+W2+W3

情况4 当n≡3(mod4)时，容易计算，若n=7，则W(G)=189。

若n≥11，则对于给定顶点vi到其它顶点vj(j≠i)的距离有

顶点vi到其它顶点vj(j≠i)的距离之和为

再由图G的结构对称性，走遍所有顶点vi(1≤i≤n)，得出任意2个不同顶点之间的距离之和为

对于给定顶点ui到其它顶点uj(j≠i)的距离有

若uj∈{u(i-k)(mod n)，u(i+k)(mod n)}，1≤k≤4，则dG(ui，uj)=k

顶点ui到其它顶点uj(j≠i)的距离之和为

再由图G的结构对称性，走遍所有顶点ui(1≤i≤n)， 得出任意2个不同顶点之间的距离之和为

对于给定顶点ui到其它顶点vj的距离有

从而顶点ui到其它顶点vj的距离之和为

再由图G的结构对称性，走遍所有顶点ui(1≤i≤n)，得出任意2个不同顶点之间的距离之和为

综上所述，有

W(G)=W1+W2+W3

根据以上1、2、3、4情况，定理结论成立。定理1证毕。

3 结 论

广义Petersen图是一类重要的并被广泛研究的互联网络拓扑结构，而Wiener指标作为一个重要的拓扑指数在化学研究中用来研究分子的结构。本文主要研究了广义Petersen图的Wiener指标。该研究方法还可以计算出更多三正则图类。同时也可以启发进一步探索对称性较强的图类的Wiener指标的计算问题。