Pure Mathematics
Vol.07 No.03(2017), Article ID:20634,7 pages
10.12677/PM.2017.73025

The Minimal Trees of Steiner Wiener Index with Given Matching Number

Zhongzhu Liu, Li He

Mathematics and Big Data College, Huizhou University, Huizhou Guangdong

Received: May. 4th, 2017; accepted: May 19th, 2017; published: May 24th, 2017

ABSTRACT

The Steiner distance of a vertex set S is defined as the minimum number of edges of a tree whose vertex set contains a 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 determine the minimal value of in the class of trees with given matching number.

Keywords:Steiner Distance, Tree, Matching Number

给定匹配数的Steiner Wiener指数极小树

刘中柱,何莉

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

收稿日期:2017年5月4日;录用日期:2017年5月19日;发布日期:2017年5月24日

摘要

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

关键词 :Steiner距离,树,匹配数

Copyright © 2017 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/

1. 引言

是一个简单连通图,其中分别是图的点集与边集,且。图中任意两点间的距离定义为连通的最短路的长度,Wiener指数定义为:

在化学理论中,基于分子图的顶点间距离的拓扑指数对刻画分子图以及建立分子结构和特征间的关系有重要作用,同时被广泛用于预测化合物的物理化学性质和生物活性。Wiener指数是研究最为广泛的拓扑指数之一,它用于考察烷烃的沸点与分子结构的关系,同时也用于分析交通网络与社交网络。相关的结果参考文献 [1] - [16] 。

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

是连通图,则等于生成树的边数,即.Dankelmann, Oellermann, Swart [17] 提出了k-Steiner平均距离的概念,其中

随后李学良,毛亚平,Gutman在文献 [18] 中提出了k-Steiner Wiener指数的概念,其中

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

2. 预备知识

图中不相邻的边的集合称为图的一个匹配,而边数最多的匹配称为图的最大匹配。设是图的一个最大匹配,称中元素的个数为图的匹配数,若饱和图的每个顶点,称图为完美匹配图。令个顶点,且匹配数为的树的集合,其中.

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

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

引理2.2. 若是连通的,则.

M. Kovse [19] 给出以下关于树的Steiner Wiener指数边的表达公式。

引理2.3. 若个顶点的树,则

其中分别是后两个连通分支的点数。

证明:由 [19] 的结果可知

证毕。

3. 主要结果

引理3.1. 若,且,如图1 (Figure 1)所示,令的变换称为I-变换,则对任意正整数,有

Figure 1. The I-transformation of Lemma 3.1

图1. 引理3.1中的I-变换

证明:由于树的每一条边都是割边,取,则不妨设的二个连通块的点数分别为,则有,若中的点与边取相同的标号,由引理2.3可知:

任取边,则有

,由于,不妨设,从而有

证毕。

引理3.2. 若,且,如图2 (Figure 2)所示,令的变换称为II-变换,对任意正整数,有

证明:由于树的每一条边都是割边,取,则不妨设的二个连通块的点数分别为,则有,若中的点与边取相同的标号,由引理2.3可知:

任取边,则有

,由于,从而有

Figure 2. The II-transformation of Lemma 3.2

图2. 引理3.2中的II-变换

以下对分情况讨论:

情况1:若,显然有.

情况2:若,则有

情况3:若,不妨设,则有

综合情况1、2、3,得到结果。证毕。

图3 (Figure 3)所示,令是对星图中的个悬挂点分别与一个新的点连边得到的树,易知,从而对任一树,可通过引理3.1和3.2当中的I-,II-变换,逐步变换成,从而有以下定理:

定理3.1. 若,对任意正整数,有

Figure 3. The extremal graph of Theorem 3.1

图3. 定理3.1中的极图

基金项目

本文受广东省自然科学基金(No. 2014A030310119)、国家社会科学基金(No. 15BTJ024)和惠州市科技创新基金(No. 2014B020004027)资助。

文章引用

刘中柱,何莉. 给定匹配数的Steiner Wiener指数极小树
The Minimal Trees of Steiner Wiener Index with Given Matching Number[J]. 理论数学, 2017, 07(03): 193-199. http://dx.doi.org/10.12677/PM.2017.73025

参考文献 (References)

  1. 1. 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.

  2. 2. Dobrynin, A., Entringer, R. and Gutman, I. (2001) Wiener Index of Trees: Theory and Application. Acta Applicandae Mathematicae, 66, 211-249.

  3. 3. Du, Z. and Zhou, B. (2010) Minimum Wiener Indices of Trees and Unicyclic Graphs of Given Matching Number. MATCH Communications in Mathematical and in Computer Chemistry, 63, 101-112.

  4. 4. 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

  5. 5. 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

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

  7. 7. Gutman, I. and Zhang, S. (2006) Graph Connectivity and Wiener Index. Bulletin Classe des Sciences Mathematiques et Natturalles, 133, 1-5.

  8. 8. Yeh, H.-G. and Chang, G.J. (1996) Weighted Connected Domination and Steiner Trees in Distance-Hereditary Graphs. In: Graph Theory-Combinatorics and Computer Science, Vol. 1120 of the series Lecture Notes in Computer Science, 48-52.

  9. 9. 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.

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

  11. 11. 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

  12. 12. 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.

  13. 13. 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.

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

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

  16. 16. 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 Ma-thematical and in Computer Chemistry, 71, 461-508.

  17. 17. 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

  18. 18. Li, X., Mao, Y. and Gutman, I. (2016) The Steiner Wiener Index of a Graph. Discussiones Mathematicae Graph Theory, 36, 455-465.

  19. 19. Kovse, M. (2016) Vertex Decomposition of the Steiner Wiener Index and the Steiner Betweenness Centrality. arXiv:1605.00260v2 [math.CO].

  20. 20. Ali, P., Dankelmann, P. and Mukwembi, S. (2012) Upper Bounds on the Steiner Diameter of a Graph. Discrete Applied Mathematics, 160, 1845-1850.

  21. 21. Caceresa, J., Marquezb, A. and Puertasa, M.L. (2008) Steiner Distance and Convexity in Graphs. European Journal of Combinatorics, 29, 726-736.

  22. 22. Chartrand, G., Oellermann, O.R., Tian, S. and Zou, H.B. (1989) Steiner Distance in Graphs. Časopis pro Pěstování Matematiky, 114, 399-410.

  23. 23. 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.

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

  25. 25. 刘中柱, 程晓胜. Steiner Wiener指数与图的参数[J]. 应用数学进展, 2016, 5(4): 747-453.

期刊菜单