Steiner Wiener指数与图的参数
Steiner Wiener Index and Graph Parameters
DOI: 10.12677/AAM.2016.54086, PDF, HTML, XML,  被引量 下载: 1,851  浏览: 2,343  国家科技经费支持
作者: 刘中柱, 程晓胜：惠州学院数学与大数据学院，广东 惠州
关键词: Steiner树；Steiner Wiener指数；点染色数；匹配数；Steiner Tree； Steiner Wiener Index； Chromatic Number； 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 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 SWk(G) of G is defined as the sum of d(S) among all possible k-vertex set S of G. In this paper, we give the bounds of SWk(G) in the classes of graphs with given chromatic number or matching number, and characterize the extremal graphs.
文章引用：刘中柱, 程晓胜. Steiner Wiener指数与图的参数[J]. 应用数学进展, 2016, 5(4): 747-753. http://dx.doi.org/10.12677/AAM.2016.54086

参考文献

[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] 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] 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] 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] 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] Zhou, B. (2005) Modified Wiener Indices of Thorn Trees. Kragujevac Journal of Mathematics, 27, 5-9.
[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] Berge, C. (1958) Sur le couplage maximum dun graphe. C. R. Acad. Sci. Paris Ser. I. Math., 247, 258-259.
[9] Buckley, F. and Harary, F. (1990) Distance in Graphs. Addison-Wesley, Redwood.
[10] Chartrand, G., Oellermann, O.R., Tian, S. and Zou, H.B. (1989) Steiner Distance in Graphs. Casopis Pest. Mat., 114, 399-410.
[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] Entringer, R.C., Jackson, D.E. and Snyder, D.A. (1976) Distance in Graphs. Czechoslovak Mathematical Journal, 26, 283-296.
[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] 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] 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] Kovse, M. (2016) Vertex Decomposition of Steiner Wiener Index and Steiner Betweenness Centrality. arxiv: 1605.00260.
[17] Chartrand, G. and Zhang, P. (2008) Chromatic Graph Theory. CRC Press, Boca Raton.
https://doi.org/10.1201/9781584888017
[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] 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] 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] 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] 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] 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] 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] 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] 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] 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] 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] 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

为你推荐