Geodesic
Inverse Problem on the Steiner Wiener Index
Discussiones Mathematicae. Graph Theory, Tome 38 (2018) no. 1, pp. 83-95.

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_G(u, v), where d_G(u, v) is the distance (the length a shortest path) between the vertices u and v in G. For S ⊆ V (G), the Steiner distance d(S) of the vertices of S, introduced by Chartrand et al. in 1989, is the minimum size of a connected subgraph of G whose vertex set contains S. The k-th Steiner Wiener index SW_k(G) of G is defined as SW_k(G)= Σ_ S ⊆ V(G) |S|=k d(S). We investigate the following problem: Fixed a positive integer k, for what kind of positive integer w does there exist a connected graph G (or a tree T) of order n ≥ k such that SW_k(G) = w (or SW_k(T) = w)? In this paper, we give some solutions to this problem.
Keywords: distance, Steiner distance, Wiener index, Steiner Wiener index 
@article{DMGT_2018_38_1_a6,
     author = {Li, Xueliang and Mao, Yaping and Gutman, Ivan},
     title = {Inverse {Problem} on the {Steiner} {Wiener} {Index}},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {83--95},
     publisher = {mathdoc},
     volume = {38},
     number = {1},
     year = {2018},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2018_38_1_a6/}
}
TY  - JOUR
AU  - Li, Xueliang
AU  - Mao, Yaping
AU  - Gutman, Ivan
TI  - Inverse Problem on the Steiner Wiener Index
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2018
SP  - 83
EP  - 95
VL  - 38
IS  - 1
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DMGT_2018_38_1_a6/
LA  - en
ID  - DMGT_2018_38_1_a6
ER  - 
%0 Journal Article
%A Li, Xueliang
%A Mao, Yaping
%A Gutman, Ivan
%T Inverse Problem on the Steiner Wiener Index
%J Discussiones Mathematicae. Graph Theory
%D 2018
%P 83-95
%V 38
%N 1
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DMGT_2018_38_1_a6/
%G en
%F DMGT_2018_38_1_a6
Li, Xueliang; Mao, Yaping; Gutman, Ivan. Inverse Problem on the Steiner Wiener Index. Discussiones Mathematicae. Graph Theory, Tome 38 (2018) no. 1, pp. 83-95. http://geodesic.mathdoc.fr/item/DMGT_2018_38_1_a6/

[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] E.O.D. Andriantiana, S. Wagner and H. Wang, Maximum Wiener index of trees with given segment sequence, MATCH Commun. Math. Comput. Chem. 75 (2016) 91–104.

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

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

[5] J. Cáceres, A. Márquez and M.L. Puertas, 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.L. Tian and H.B. Zou, Steiner distance in graphs, Časopis Pest. Mat. 114 (1989) 399–410.

[7] L. Chen, X. Li and M. Liu, The ( revised ) Szeged index and the Wiener index of a nonbipartite graph, European J. Combin. 36 (2014) 237–246. doi:10.1016/j.ejc.2013.07.019

[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:1〈15::AID-JGT3〉3.0.CO;2-O

[9] P. Dankelmann, O.R. Oellermann and H.C. Swart, 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 applications, 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] J. Fink, B. Lužar and R. Škrekovski, Some remarks on inverse Wiener index problem, Discrete Appl. Math. 160 (2012) 1851–1858. doi:10.1016/j.dam.2012.02.028

[13] W. Goddard and O.R. Oellermann, Distance in graphs, in: M. Dehmer (Ed.), Structural Analysis of Complex Networks (Birkhäuser, Dordrecht, 2011) 49–72. doi:10.1007/978-0-8176-4789-6_3

[14] M. Goubko, Minimizing Wiener index for vertex-weighted trees with given weight and degree sequences, MATCH Commun. Math. Comput. Chem. 75 (2016) 3–27.

[15] I. Gutman, R. Cruz and J. Rada, Wiener index of Eulerian graphs, Discrete Appl. Math. 162 (2014) 247–250. doi:10.1016/j.dam.2013.08.024

[16] 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

[17] I. Gutman, K. Xu and M. Liu, A congruence relation for Wiener and Szeged indices, Filomat 29 (2015) 1081–1083. doi:10.2298/FIL1505081G

[18] I. Gutman and Y.N. Yeh, The sum of all distances in bipartite graphs, Math. Slovaca 45 (1995) 327–334.

[19] I. Gutman, Y.N. Yeh and J.C. Chen, On the sum of all distances in graphs, Tamkang J. Math. 25 (1994) 83–86.

[20] M. Knor and R. Škrekovski, Wiener index of generalized 4- stars and of their quadratic line graphs, Australas. J. Combin. 58 (2014) 119–126.

[21] M. Krnc and R. Škrekovski, On Wiener inverse interval problem, MATCH Commun. Math. Comput. Chem. 75 (2016) 71–80.

[22] M. Lepović and I. Gutman, A collective property of trees and chemical trees, J. Chem. Inf. Comput. Sci. 38 (1998) 823–826. doi:10.1021/ci980004b

[23] X. Li, Y. Mao and I. Gutman, The Steiner Wiener index of a graph, Discuss. Math. Graph Theory 36 (2016) 455–465. doi:10.7151/dmgt.1868

[24] Y. Mao, Z. Wang and I. Gutman, Steiner Wiener index of graph products, Trans. Comb. 5 (2016) 39–50.

[25] Y. Mao, Z. Wang, Y. Xiao and C. Ye, Steiner Wiener index and connectivity of graphs, Util. Math., in press.

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

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

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

[29] S.G. Wagner, A note on the inverse problem for the Wiener index, MATCH Commun. Math. Comput. Chem. 64 (2010) 639–646.

[30] S.G. Wagner, A class of trees and its Wiener index, Acta Appl. Math. 91 (2006) 119–132. doi:10.1007/s10440-006-9026-5

[31] S.G. Wagner, H. Wang and G. Yu, Molecular graphs and the inverse Wiener index problem, Discrete Appl. Math. 157 (2009) 1544–1554. doi:10.1016/j.dam.2008.06.008

[32] H. Wang and G. Yu, All but 49 numbers are Wiener indices of trees, Acta Appl. Math. 92 (2006) 15–20. doi:10.1007/s10440-006-9037-2

[33] 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.