Steiner Wiener指数与图的参数

Steiner Wiener Index and Graph Parameters

摘要: 本文讨论了给定点着色数和匹配数的图类中k-Steiner Wiener指数的下界，并刻画了极图。图G 的k-Steiner Wiener指数定义为图G 中任意k-点集S 的Steiner距离的d(S)和，而点集S 的Steiner距离d(S)是包含点集S 的最小子树的边的数目。

Abstract: The Steiner distance d(S) of vertex set S is defined as the minimum number of edges of a tree whose vertex set contains vertex set S, and the Steiner k-Wiener index SW_k(G) of G is defined as the sum of d(S) among all possible k-vertex set S of G. In this paper, we give the bounds of SW_k(G) in the classes of graphs with given chromatic number or matching number, and characterize the extremal graphs.

1. 引言

设是一个简单图，其中分别是图的点集与边集，且。图中任意两点间的距离定义为连通的最短路的长度，Wiener指数定义为，Wiener指数是图的一个拓扑参数，它常用于分析分子的分枝数，同时也用于分析交通网络与社交网络。相关的结果参考文献 [1] - [16] 。

点集的Steiner距离定义为图中包含点集的最小子树的边数，Steiner距离是经典的组合优化问题，最早可以追溯到17世纪初。1634年，数学家Fermat提出这样一个问题：在欧氏平面上有三个点，寻找一个点使得由该点连接三个点的距离之和最小。后经多位数学家扩展补充，最后以瑞士数学家Steiner的名字命名为Steiner问题。由于Steiner距离在现代生产生活中应用十分广泛，因此多年来是研究的热点，本文讨论图的Steiner距离问题。

若是连通图，则等于生成树的边数，即。李学良，毛亚平，Gutman在文献 [17] 中提出了k-Steiner Wiener指数的概念，其中

，

且。Dankelmann，Oellermann，Swart [18] 提出了k-Steiner平均距离的概念，其中

。

Dankelmann，Oellermann，Swart在文献 [19] 中得到给定点数的树中的上下界，李学良等人在文献 [19] 中给出了树的指数计算公式，M. Kovse进一步得到树的的点和边的表达公式。与Steiner距离的拓扑指数相关的结果可参考文献 [10] [20] - [26] 。由于图的计算是NP完全问题 [27] ，讨论特殊图类的上下界与极图问题显得十分重要，本文将重点讨论二种图类。

图的染色数是使得中任何相邻两点均染不同色的最小颜色数，而图的匹配是边的集合，任意两条边没有公共点。图的最大匹配是所有匹配中所含匹配边数最多的匹配，图的匹配数定义为图中最大匹配所含的边的数目。本文讨论了给定染色数或匹配数的图类中Steiner Wiener指数的下界，并刻画了极图。

2. 预备知识

边集定义为图中点集间的相连的边的集合，点集的导出子图定义为以为点集，两端点均在中的边的全体为边集的子图。定义为图与图的并集，而是对中的任一点与的任一点进行连边得到的图。为个点的完全图，为多部图， -图兰图是多部图，且对任意的，有。点-染色临界图定义为染色数为，且任删一点使得染色数的图。若在图中，任意删掉条边得到的子图仍连通，删掉条边不连通的图，称为-边连通图。

令为所有点数为，点染色数为的图的集合，为所有点数为，匹配数为的图的集合。若是实数，定义为的整数部分。

若图中的一个连通块的点数为奇(偶)数，则称该连通块为奇(偶)连通块。令为图中奇连通块的个数，则由Tutte-Berge公式 [13] [28] 可知，

。

为了进一步讨论Steiner Wiener指数，根据Steiner距离的定义，得到以下引理：

引理 2.1. 若是连通图中的任两点，且，则，其中是在中增加边得到的新图。

引理 2.2. 若，是连通的，则。

3. 给定染色数的图类

图的染色数在危险品存储、物流分配等方面有广泛的应用，而在物流运输中的路径设计显得尤为重要，本节讨论给定染色数的图类中的下界与相关的极图。

引理 3.1. [29] 若是-点染色临界图，则是-边连通图。

定理 3.1. 若是-点染色临界图，其中的顶点数是，。若或，则有

。

证明：若是-点染色临界图，则由引理3.1，的边连通度是。令，，其中或，从而。

若不连通，则存在至少二个连通块，设是的一个连通块，从而有图是不连通的。令，从而有，，综上，

，

经计算可得，与假设矛盾，故连通。

已知连通，由引理2.2，，且，证毕。

定理 3.2. 若，其中。

，

当是-图兰图时，等号成立。

证明：令为中Steiner Wiener指数值最小的图之一。由染色数的定义可知，可划分成个点独立集，其中，。由引理2.1可知，在中，若二个非邻接点在不同点独立集中，则二点间连边不会增加值，从而有。以下假设。

令，。点集可分成二类：连通或不连通。

(1) 若连通，则，即存在，使得，由引理2.2，，且

。

(2) 若不连通，则存在，使得。由的结构可知，任选，有是连通图，由引理2.2，，且

。

综上(1)、(2)可知，

。

若不是图兰图，则存在正整数，使得。令，则

，

等号成立当且仅当。故图兰图是中Steiner Wiener指数极小图之一，从而有

，

证毕。

4. 给定匹配数的图类

图的匹配在交通网络、社交网络等方面有广泛的应用，本节讨论给定匹配数的图类中的下界，并刻画了极图。

定理 4.1. 若，其中，。则

(1) 若，则，当时，等号成立；

(2) 若，则，当时，等号成立。

证明：令为中Steiner Wiener指数值最小的图之一，则由Tutte-Berge公式可知，存在点集，使得。

令，，则。

假设，则，。若，则。若，则。

根据引理2.1，增边不会增加值，从而有。

假设，则有。令为中所有奇连通块。若含有偶连通块，则在偶连通块与某个奇连通块间连边，得到新图，其中满足性质

，。

由引理2.1可知，。从而可知不含偶连通块。同理，由引理2.1可知，和的点导出子图是完全图，且中每一顶点与中的每一顶点有边相连，因此。

以下计算。令，，，，其中。令，。易知点集可分成二类：连通或不连通。

(1) 若连通，则或，其中。由引理2.2可知，，从而有

。

(2) 若不连通，则有，，其中。任选，有连通，从而，且

综合(1)、(2)可知，

。

假设，其中，。不失一般性，假设，令，从而有

这与的最小性相矛盾，从而，证毕。

基金项目

本文受广东省自然科学基金(No. 2016A030313122, 2015A030310410)、国家社会科学基金(No. 15BTJ024)、惠州市科技创新基金(No. 2014B020004027)和惠州学院优秀青年培育项目(No. 20160224082617206)资助。