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)资助。
参考文献