Geodesic
The Steiner Wiener Index of A Graph
Discussiones Mathematicae. Graph Theory, Tome 36 (2016) no. 2, pp. 455-465.

Voir la notice de l'article provenant de la source Library of Science

The Wiener index W(G) of a connected graph G, introduced by Wiener in 1947, is defined as W(G) = Σ_ u,v ∈ V(G) d(u, v) where d_G(u, v) is the distance between vertices u and v of G. The Steiner distance in a graph, introduced by Chartrand et al. in 1989, is a natural generalization of the concept of classical graph distance. For a connected graph G of order at least 2 and S ⊆ V (G), the Steiner distance d(S) of the vertices of S is the minimum size of a connected subgraph whose vertex set is S. We now introduce the concept of the Steiner Wiener index of a graph. The Steiner k-Wiener index SW_k(G) of G is defined by Σ_ S ⊆ V(G) |S| = k d(S). Expressions for SW_k for some special graphs are obtained. We also give sharp upper and lower bounds of SW_k of a connected graph, and establish some of its properties in the case of trees. An application in chemistry of the Steiner Wiener index is reported in our another paper.
Keywords: distance, Steiner distance, Wiener index, Steiner Wiener k- index 
@article{DMGT_2016_36_2_a15,
     author = {Li, Xueliang and Mao, Yaping and Gutman, Ivan},
     title = {The {Steiner} {Wiener} {Index} of {A} {Graph}},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {455--465},
     publisher = {mathdoc},
     volume = {36},
     number = {2},
     year = {2016},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2016_36_2_a15/}
}
TY  - JOUR
AU  - Li, Xueliang
AU  - Mao, Yaping
AU  - Gutman, Ivan
TI  - The Steiner Wiener Index of A Graph
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2016
SP  - 455
EP  - 465
VL  - 36
IS  - 2
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DMGT_2016_36_2_a15/
LA  - en
ID  - DMGT_2016_36_2_a15
ER  - 
%0 Journal Article
%A Li, Xueliang
%A Mao, Yaping
%A Gutman, Ivan
%T The Steiner Wiener Index of A Graph
%J Discussiones Mathematicae. Graph Theory
%D 2016
%P 455-465
%V 36
%N 2
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DMGT_2016_36_2_a15/
%G en
%F DMGT_2016_36_2_a15
Li, Xueliang; Mao, Yaping; Gutman, Ivan. The Steiner Wiener Index of A Graph. Discussiones Mathematicae. Graph Theory, Tome 36 (2016) no. 2, pp. 455-465. http://geodesic.mathdoc.fr/item/DMGT_2016_36_2_a15/

[1] P. Ali, P. Dankelmann and S. Mukwembi, Upper bounds on the Steiner diameter of a graph, Discrete Appl. Math. 160 (2012) 1845-1850. doi:10.1016/j.dam.2012.03.031

[2] Y. Alizadeh, V. Andova, S. Klavžar and R. Škrekovski, Wiener dimension: Fundamental properties and (5, 0)-nanotubical fullerenes, MATCH Commun. Math. Comput. Chem. 72 (2014) 279-294.

[3] J.A. Bondy and U.S.R. Murty, Graph Theory (Springer, 2008).

[4] F. Buckley and F. Harary, Distance in Graphs (Addison-Wesley, Redwood, 1990).

[5] J. Cáceresa, A. Márquezb and M.L. Puertasa, Steiner distance and convexity in graphs, European J. Combin. 29 (2008) 726-736. doi:10.1016/j.ejc.2007.03.007

[6] G. Chartrand, O.R. Oellermann, S. Tian and H.B. Zou, Steiner distance in graphs, Časopis Pest. Mat. 1 1 4 ( 1989) 399-410.

[7] C.M. da Fonseca, M. Ghebleh, A. Kanso and D. Stevanović, Counterexamples to a conjecture on Wiener index of common neighborhood graphs, MATCH Commun. Math. Comput. Chem. 72 (2014) 333-338.

[8] P. Dankelmann, O.R. Oellermann and H.C. Swart, The average Steiner distance of a graph, J. Graph Theory 22 (1996) 15-22. doi:10.1002/(SICI)1097-0118(199605)22:1h15::AID-JGT3i3.0.CO;2-O

[9] P. Dankelmann, H.C. Swart and O.R. Oellermann, On the average Steiner distance of graphs with prescribed properties, Discrete Appl. Math. 79 (1997) 91-103. doi:10.1016/S0166-218X(97)00035-8

[10] A. Dobrynin, R. Entringer and I. Gutman, Wiener index of trees: theory and application, Acta Appl. Math. 66 (2001) 211-249. doi:10.1023/A:1010767517079

[11] R.C. Entringer, D.E. Jackson and D.A. Snyder, Distance in graphs, Czechoslovak Math. J. 26 (1976) 283-296.

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

[13] W. Goddard and O.R. Oellermann, Distance in graphs, in: Structural Analysis of Complex Networks, M. Dehmer (Ed.), (Birkhäuser, Dordrecht, 2011) 49-72.

[14] I. Gutman, B. Furtula and X. Li, Multicenter Wiener indices and their applications, J. Serb. Chem. Soc. 80 (2015) 1009-1017. doi:10.2298/JSC150126015G

[15] I. Gutman, S. Klavžar and B. Mohar, Fifty years of the Wiener index, MATCH Commun. Math. Comput. Chem. 35 (1997) 1-159.

[16] I. Gutman and O.E. Polansky, Mathematical Concepts in Organic Chemistry (Springer, Berlin, 1986).

[17] Y.L. Jin and X.D. Zhang, On two conjectures of the Wiener index, MATCH Commun. Math. Comput. Chem. 70 (2013) 583-589.

[18] S. Klavžar and M.J. Nadjafi-Arani, Wiener index in weighted graphs via unification of __-classes, European J. Combin. 36 (2014) 71-76. doi:10.1016/j.ejc.2013.04.008

[19] M. Knor and R. Škrekovski, Wiener index of generalized 4-stars and of their quadratic line graphs, Australas. J. Combin. 58 (2014) 119-126. doi:10.1002/jgt.3190140510

[20] O.R. Oellermann and S. Tian, Steiner centers in graphs, J. Graph Theory 14 (1990) 585-597. doi:/10.1002/jgt.3190140510

[21] D.H. Rouvray, Harry in the limelight: The life and times of Harry Wiener, in: Topology in Chemistry-Discrete Mathematics of Molecules, D.H. Rouvray, R.B. King (Eds.), (Horwood, Chichester, 2002) 1-15.

[22] D.H. Rouvray, The rich legacy of half century of the Wiener index, in: Topology in Chemistry-Discrete Mathematics of Molecules, D.H. Rouvray and R.B. King (Eds.), (Horwood, Chichester, 2002) 16-37.

[23] H. Wiener, Structural determination of paraffin boiling points, J. Amer. Chem. Soc. 69 (1947) 17-20. doi:10.1021/ja01193a005

[24] K. Xu, M. Liu, K.C. Das, I. Gutman and B. Furtula, A survey on graphs extremal with respect to distance-based topological indices, MATCH Commun. Math. Comput. Chem. 71 (2014) 461-508.