给定匹配数的Steiner Wiener指数极小树
The Minimal Trees of Steiner Wiener Index with Given Matching Number
DOI: 10.12677/PM.2017.73025, PDF, HTML, XML, 下载: 1,536  浏览: 2,486  科研立项经费支持
作者: 刘中柱*, 何莉：惠州学院数学与大数据学院，广东 惠州
关键词: Steiner距离；树；匹配数；Steiner Distance； Tree； Matching Number
摘要: 本文讨论了给定匹配数的树中k-Steiner Wiener指数的极小值，并刻画了极图。图G的k-Steiner Wiener指数定义为图G中任意k-点集S的Steiner距离d(S)的和，而点集S的Steiner距离d(S) 是包含点集S的最小子树的边的数目。
Abstract: 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. https://doi.org/10.12677/PM.2017.73025

参考文献

[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.
https://doi.org/10.1007/978-0-8176-4789-6_3
[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] 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.
https://doi.org/10.1002/jgt.3190140510
[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.
https://doi.org/10.1021/Ja01193a005
[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] 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.
https://doi.org/10.1002/(SICI)1097-0118(199605)22:1<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.

为你推荐