﻿ 给定匹配数的Steiner Wiener指数极小树 The Minimal Trees of Steiner Wiener Index with Given Matching Number

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

1. 引言

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

2. 预备知识

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

3. 主要结果

Figure 1. The I-transformation of Lemma 3.1

，由于，不妨设，从而有

，由于，从而有

Figure 2. The II-transformation of Lemma 3.2

Figure 3. The extremal graph of Theorem 3.1

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

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.