分裂图的Wiener指标

李亚平，唐子兴

(喀什大学数学与统计学院，84400，新疆，喀什)

0 引言

本文所考虑的图都是连通的、简单的、有限图。设G=(V,E)是顶点集为V，边集为E的有限简单图，用v(G)和e(G)分别记图G中的顶点数和边数。设Kn记为n个顶点的完全图。对u,v∈v(G)，顶点u和v之间的距离dG(u,v)是这2个点之间最短路的长度。图的直径是G中所有点对之间距离的最大值，也就是max{d(u,v|u,v∈v(G))}。

Wiener指标由Wiener于1947年提出[1]，最初用来预测石蜡的沸点，但在理论和实践方面都得到了广泛的研究，文献[2-5]并且也从纯粹的图论观点做了研究，连通图G的Wiener指标是一个图不变量，即在图的所有可能同构下所保留的性质。定义为G中所有无序对顶点之间的距离之和：

关于Wiener指标大量的研究是在文献[6-9,10-12]中积累起来的，这里仅举几个最近的例子。

图G的一个团是G的一个完全子图；图的独立集是不相邻的顶点组成的集合。分裂图是它的顶点能划分成一个团C和一个独立集I(可能为空)。设G=(C∪I,E)是分裂图，这里C={u1,u2,…，uk}是团，I={v1,v2,…,vn-k}是独立集，C的顶点与I的顶点之间没有边的限制，它们之间可以任意连边。分裂图在过去的几年里得到了广泛的研究[13-15]。众所周知，对于n个顶点的任何连通图G都有结果：

很明显，Kn是一个分裂图，因此很容易得出Kn是n阶的所有分裂图中Wiener指标最小的图。

1 主要结果

1.1 连通分裂图

由文献[16]中得到的灵感，在这一节给出了分裂图的结构使其具有最大的Wiener指标，其中结构的意思是，分裂图G=(C∪I,E)中团的顶点个数以及独立集I的顶点如何连接到团。从上面的描述中，很容易看到，当k

证明：设W(G,I)是分裂图G的Wiener指标，这里I是一个k-部图，每个部分的大小分别为x1,x2,…,xk；如果这些部分的大小不相等也不几乎相等，则存在xs-xt>1；考虑如下的一个k-部图I′，它的k部分的顶点数分别为x1,x2,…,xs-1,…,xt+1,…,xk，则

因此

W(G,I′)-W(G,I)=xs-xt-1≥xt+2-xt-1=1。

证毕。

由上面得到I中的点对之间dI(vi,vj)=3当且仅当vi和vj在不同的部。提出一个概念，n个顶点的简单完全k部图，其中所有部的大小尽可能相等，称为Turán图，记为Tk,n。结合上面的结果，有以下。

定理1：设连通的分裂图G是由k个点的团C和所有部的大小尽可能相等的k-部构成的，这里每个部的点共同连接在团C的一个顶点上，不同部的顶点不能连在同一个点上，则

证明：设图G的k个部分的大小分别为x1,x2,…,xk，则

由以上结果能得到直径为3、阶数为n的分裂图，团的顶点数为多少时，有最大的Wiener指标。很明显，从Wiener指标的定义可以看出，对所有图G有

这里diam(G)是图G的直径。

1.2 2-连通分裂图

观察1：设G=(C∪I,E)是一个2-连通的分裂图，如果G有最大的Wiener指标，则团C是偶的。

证明：假如C是奇的，把团C的顶点移给I一个，则图G的Wiener指标将增加。