PM  >> Vol. 7 No. 3 (May 2017)

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

  • 全文下载: PDF(398KB) HTML   XML   PP.193-199   DOI: 10.12677/PM.2017.73025  
  • 下载量: 140  浏览量: 208   科研立项经费支持


刘中柱,何莉:惠州学院数学与大数据学院,广东 惠州

Steiner距离匹配数Steiner Distance Tree Matching Number


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

The Steiner distance d(S) 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 SKW(G) of G is defined as the sum of d(S) among all possible k-vertex set S of G. In this paper, we determine the minimal value of SKW(G) in the class of trees with given matching number.

刘中柱, 何莉. 给定匹配数的Steiner Wiener指数极小树[J]. 理论数学, 2017, 7(3): 193-199.


[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] Dobrynin, A., Entringer, R. and Gutman, I. (2001) Wiener Index of Trees: Theory and Application. Acta Applicandae Mathematicae, 66, 211-249.
[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] Goddard, W. and Oellermann, O.R. (2011) Distance in Graphs. In: Dehmer, M., Ed., Structural Analysis of Complex Networks, Birkhauser, Dordrecht, 49-72.
[5] Gutman, I., Furtula, B. and Li, X. (2015) Multicenter Wiener Indices and Their Applications. Journal of the Serbian Chemical Society, 80, 1009-1017.
[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] Gutman, I. and Zhang, S. (2006) Graph Connectivity and Wiener Index. Bulletin Classe des Sciences Mathematiques et Natturalles, 133, 1-5.
[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] 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] Kovse, M. (2016) Vertex Decomposition of Steiner Wiener Index and Steiner Betweenness Centrality. arxiv: 1605.00260
[11] Oellermann, O.R. and Tian, S. (1990) Steiner Centers in Graphs. Journal of Graph Theory, 14, 585-597.
[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] 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] Wiener, H. (1947) Structural Determination of Paraffin Boiling Points. Journal of the American Chemical Society, 69, 17-20.
[15] Tutte, W.T. (1947) The Factorization of Linear Graphs. Journal of the London Mathematical Society, 22, 107-111.
[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] Dankelmann, P., Oellermann, O.R. and Swart, H.C. (1996) The Average Steiner Distance of a Graph. Journal of Graph Theory, 22, 15-22.<15::AID-JGT3>3.0.CO;2-O
[18] Li, X., Mao, Y. and Gutman, I. (2016) The Steiner Wiener Index of a Graph. Discussiones Mathematicae Graph Theory, 36, 455-465.
[19] Kovse, M. (2016) Vertex Decomposition of the Steiner Wiener Index and the Steiner Betweenness Centrality. arXiv:1605.00260v2 [math.CO].
[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] Caceresa, J., Marquezb, A. and Puertasa, M.L. (2008) Steiner Distance and Convexity in Graphs. European Journal of Combinatorics, 29, 726-736.
[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] 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] 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] 刘中柱, 程晓胜. Steiner Wiener指数与图的参数[J]. 应用数学进展, 2016, 5(4): 747-453.