一类图变换对其维纳指标与离心率之差的影响

林雅津,王月卿

（1.闽南师范大学数学与统计学院,福建漳州363000；2.闽南师范大学计算机学院,福建 漳州363000）

本文所讨论的均为简单连通图，设G=(V(G),E(G))，其中顶点集为V(G)，边集为E(G).用n(G)和m(G)分别表示图G的顶点数和边数.对任意u,v∈V(G)，用dG(u,v)表示G中u和v之间的最短距离.用dG(v)表示顶点v到G中其余顶点的距离之和，即分别用deg(v)和ω(G)表示顶点v的度和图G的连通分支个数.若边e∈E(G)满足ω(G-e)>ω(G)，则称e为连通图G的一条割边.对于图G的某一割边e=uv∈E(G)，分别用n(Gu)，n(Gv)表示G中分布在e两侧的顶点数目.

图的维纳指标是1947年由著名的化学家Wiener[1]提出的基于距离不变量的拓扑指标，其定义是图中所有不同顶点对间的距离和，即

关于图维纳指标的研究和进展可参考文献[1-6].

对v∈V(G)，顶点v在G中的离心率εG(v)是v与G中其他任意点的最大距离,即

定义G中最大的顶点离心率为直径，用diam(G)表示；最小的顶点离心率为半径，用rad(G)表示.

图G的离心率为G中所有点的离心率之和，用ε(G)表示.因此

关于图的总离心率和平均离心率的研究和进展可参考文献[7-9].若e∈E(G)，令G⋅e表示图G通过收缩边e之后而得到的图，显然n(G)=n(G⋅e)+1，如图1所示.

图1 图G和G⋅eFig.1 The graph G and graph G⋅e

1 预备知识

Darabi[10]研究了G和G⋅e的维纳指标和离心率之间差的关系，得到了以下结论.

定理1[10]设G为具有n(G)≥3个顶点的简单连通图，e∈E(G)是G的某一割边,则

同时提出了以下猜想.

猜想1[11]设G为具有n(G)≥3个顶点的简单连通图，则对于任意e∈E(G)，有

Das[11]证明了上述猜想.

本文进一步研究图的变换对其W(G)-ε(G)的影响.设G为简单连通图，对e∈E(G)，G'为G通过收缩边e=uv成为一个新点eu并在eu上添加一个悬挂边euev而得到的图，如图2……