Advances in Applied Mathematics
Vol.05 No.04(2016), Article ID:19097,7 pages
10.12677/AAM.2016.54086

Steiner Wiener Index and Graph Parameters

Zhongzhu Liu, Xiaosheng Cheng

College of Mathematics and Data Science, Huizhou University, Huizhou Guangdong

Received: Nov. 10th, 2016; accepted: Nov. 25th, 2016; published: Nov. 29th, 2016

Copyright © 2016 by authors and Hans Publishers Inc.

This work is licensed under the Creative Commons Attribution International License (CC BY).

http://creativecommons.org/licenses/by/4.0/

ABSTRACT

The Steiner distance 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 of G is defined as the sum of among all possible k-vertex set S of G. In this paper, we give the bounds of in the classes of graphs with given chromatic number or matching number, and characterize the extremal graphs.

Keywords:Steiner Tree, Steiner Wiener Index, Chromatic Number, Matching Number

Steiner Wiener指数与图的参数

刘中柱,程晓胜

惠州学院数学与大数据学院,广东 惠州

收稿日期:2016年11月10日;录用日期:2016年11月25日;发布日期:2016年11月29日

摘 要

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

关键词 :Steiner树,Steiner Wiener指数,点染色数,匹配数

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)资助。

文章引用

刘中柱,程晓胜. Steiner Wiener指数与图的参数
Steiner Wiener Index and Graph Parameters[J]. 应用数学进展, 2016, 05(04): 747-753. http://dx.doi.org/10.12677/AAM.2016.54086

参考文献 (References)

  1. 1. Gutman, I. and Zhang, S. (2006) Graph Connectivity and Wiener Index, Bulletin T.CXXXIII de l' Academie serbe des sciences et des arts. Classe des Sciences math ematiques et naturelles Sciences math ematiques, 133, 1-5.

  2. 2. Oellermann, O.R. and Tian, S. (1990) Steiner Centers in Graphs. Journal of Graph Theory, 14, 585-597. https://doi.org/10.1002/jgt.3190140510

  3. 3. Rouvray, D.H. (2002) Harry in the Limelight: The Life and Times of Harry Wiener. In: Rouvray, D.H. and King, R.B., Eds., Topology in Chemistry—Discrete Mathematics of Molecules, Horwood, Chichester, 1-15.

  4. 4. Tutte, W.T. (1947) The Factorization of Linear Graphs. Journal London Mathematical Society, 22, 107-111. https://doi.org/10.1112/jlms/s1-22.2.107

  5. 5. Xu, K., Liu, M., Das, K.C., Gutman, I. and Furtula, B. (2014) A Survey on Graphs Extremal with Respect to Distance- Based Topological Indices. MATCH Communications in Mathematical and in Computer Chemistry, 71, 461-508.

  6. 6. Zhou, B. (2005) Modified Wiener Indices of Thorn Trees. Kragujevac Journal of Mathematics, 27, 5-9.

  7. 7. Dankelmann, P., Oellermann, O.R. and Swart, H.C. (1996) The Average Steiner Distance of a Graph. Journal of Graph Theory, 22, 15-22. https://doi.org/10.1002/(SICI)1097-0118(199605)22:1<15::AID-JGT3>3.0.CO;2-O

  8. 8. Berge, C. (1958) Sur le couplage maximum dun graphe. C. R. Acad. Sci. Paris Ser. I. Math., 247, 258-259.

  9. 9. Buckley, F. and Harary, F. (1990) Distance in Graphs. Addison-Wesley, Redwood.

  10. 10. Chartrand, G., Oellermann, O.R., Tian, S. and Zou, H.B. (1989) Steiner Distance in Graphs. Casopis Pest. Mat., 114, 399-410.

  11. 11. Dankelmann, P., Swart, H.C. and Oellermann, O.R. (1997) On the Average Steiner Distance of Graphs with Prescribed Properties. Discrete Applied Mathematics, 79, 91-103. https://doi.org/10.1016/S0166-218X(97)00035-8

  12. 12. Entringer, R.C., Jackson, D.E. and Snyder, D.A. (1976) Distance in Graphs. Czechoslovak Mathematical Journal, 26, 283-296.

  13. 13. Garey, M.R. and Johnson, D.S. (1979) Computers and Intractability—A Guide to the Theory of NP-Completeness. Freeman, San Francisco, 208-209.

  14. 14. Gutman, I. and Polansky, O.E. (1986) Mathematical Concepts in Organic Chemistry. Springer, Berlin. https://doi.org/10.1007/978-3-642-70982-1

  15. 15. Knor, M. and Skrekovski, R. (2014) Wiener Index of Generalized 4-Stars and of Their Quadratic Line Graphs. The Australasian Journal of Combinatorics, 58, 119-126.

  16. 16. Kovse, M. (2016) Vertex Decomposition of Steiner Wiener Index and Steiner Betweenness Centrality. arxiv: 1605.00260.

  17. 17. Chartrand, G. and Zhang, P. (2008) Chromatic Graph Theory. CRC Press, Boca Raton. https://doi.org/10.1201/9781584888017

  18. 18. Hong-Gwa, Y. and Chang, G. (1998) Weighted Connected Domination and Steiner Trees in Distance-Hereditary Graphs. Discrete Applied Mathematics, 87, 245-253. https://doi.org/10.1016/S0166-218X(98)00060-2

  19. 19. Ali, P., Dankelmann, P. and Mukwembi, S. (2012) Upper Bounds on the Steiner Diameter of a Graph. Discrete Applied Mathematics, 160, 1845-1850. https://doi.org/10.1016/j.dam.2012.03.031

  20. 20. Da Fonseca, C.M., Ghebleh, M., Kanso, A. and Stevanovic, D. (2014) Counterexamples to a Conjecture on Wiener Index of Common Neighborhood Graphs. MATCH Communications in Mathematical and in Computer Chemistry, 72, 333-338.

  21. 21. Gutman, I., Furtula, B. and Li, X. (2015) Multicenter Wiener Indices and Their Applications. Journal of the Serbian Chemical Society, 80, 1009-1017. https://doi.org/10.2298/JSC150126015G

  22. 22. Gutman, I., Klavzar, S. and Mohar, B. (1997) Fifty Years of the Wiener Index. MATCH Communications in Mathematical and in Computer Chemistry, 35, 1-259.

  23. 23. Jin, Y.L. and Zhang, X.D. (2013) On Two Conjectures of the Wiener Index. MATCH Communications in Mathematical and in Computer Chemistry, 70, 583-589.

  24. 24. Caceresa, J., Marquezb, A. and Puertasa, M.L. (2008) Steiner Distance and Convexity in Graphs. European Journal of Combinatorics, 29, 726-736. https://doi.org/10.1016/j.ejc.2007.03.007

  25. 25. Wiener, H. (1947) Structural Determination of Paraffin Boiling Points. Journal of the American Chemical Society, 69, 17-20. https://doi.org/10.1021/ja01193a005

  26. 26. Li, X., Mao, Y. and Gutman, I. (2016) The Steiner Wiener Index of a Graph. Discussiones Mathematicae Graph Theory, 36, 455-465. https://doi.org/10.7151/dmgt.1868

  27. 27. Rouvray, D.H. (2002) The Rich Legacy of Half Century of the Wiener Index. In: Rouvray, D.H. and King, R.B., Eds., Topology in Chemistry—Discrete Mathematics of Molecules, Horwood, Chichester, 16-37.

  28. 28. Dobrynin, A., Entringer, R. and Gutman, I. (2001) Wiener Index of Trees: Theory and Application. Acta Applicandae Mathematicae, 66, 211-249. https://doi.org/10.1023/A:1010767517079

  29. 29. Goddard, W. and Oellermann, O.R. (2011) Distance in Graphs. In: Dehmer, M., Ed., Structural Analysis of Complex Networks, Birkhauser, Dordrecht, 49-72. https://doi.org/10.1007/978-0-8176-4789-6_3

期刊菜单