The Steiner Wiener Index of A Graph

Xueliang Li; Yaping Mao; Ivan Gutman

Discussiones Mathematicae Graph Theory (2016)

  • Volume: 36, Issue: 2, page 455-465
  • ISSN: 2083-5892

Abstract

top
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 dG(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 SWk(G) of G is defined by [...] . Expressions for SWk for some special graphs are obtained. We also give sharp upper and lower bounds of SWk 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.

How to cite

top

Xueliang Li, Yaping Mao, and Ivan Gutman. "The Steiner Wiener Index of A Graph." Discussiones Mathematicae Graph Theory 36.2 (2016): 455-465. <http://eudml.org/doc/277120>.

@article{XueliangLi2016,
abstract = {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 dG(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 SWk(G) of G is defined by [...] . Expressions for SWk for some special graphs are obtained. We also give sharp upper and lower bounds of SWk 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.},
author = {Xueliang Li, Yaping Mao, Ivan Gutman},
journal = {Discussiones Mathematicae Graph Theory},
keywords = {distance; Steiner distance; Wiener index; Steiner Wiener k- index; Steiner Wiener -index},
language = {eng},
number = {2},
pages = {455-465},
title = {The Steiner Wiener Index of A Graph},
url = {http://eudml.org/doc/277120},
volume = {36},
year = {2016},
}

TY - JOUR
AU - Xueliang Li
AU - Yaping Mao
AU - Ivan Gutman
TI - The Steiner Wiener Index of A Graph
JO - Discussiones Mathematicae Graph Theory
PY - 2016
VL - 36
IS - 2
SP - 455
EP - 465
AB - 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 dG(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 SWk(G) of G is defined by [...] . Expressions for SWk for some special graphs are obtained. We also give sharp upper and lower bounds of SWk 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.
LA - eng
KW - distance; Steiner distance; Wiener index; Steiner Wiener k- index; Steiner Wiener -index
UR - http://eudml.org/doc/277120
ER -

References

top
  1. [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 [Crossref][WoS] Zbl1245.05031
  2. [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. [3] J.A. Bondy and U.S.R. Murty, Graph Theory (Springer, 2008). 
  4. [4] F. Buckley and F. Harary, Distance in Graphs (Addison-Wesley, Redwood, 1990). Zbl0688.05017
  5. [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[Crossref] 
  6. [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. Zbl0688.05040
  7. [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. [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[Crossref] Zbl0849.05026
  9. [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[Crossref] Zbl0884.05040
  10. [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[Crossref] Zbl0982.05044
  11. [11] R.C. Entringer, D.E. Jackson and D.A. Snyder, Distance in graphs, Czechoslovak Math. J. 26 (1976) 283-296. Zbl0329.05112
  12. [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. Zbl0411.68039
  13. [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. Zbl1221.05113
  14. [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[Crossref] 
  15. [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. [16] I. Gutman and O.E. Polansky, Mathematical Concepts in Organic Chemistry (Springer, Berlin, 1986). Zbl0657.92024
  17. [17] Y.L. Jin and X.D. Zhang, On two conjectures of the Wiener index, MATCH Commun. Math. Comput. Chem. 70 (2013) 583-589. Zbl1299.05094
  18. [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 [WoS][Crossref] Zbl1284.05118
  19. [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[Crossref] Zbl1296.05060
  20. [20] O.R. Oellermann and S. Tian, Steiner centers in graphs, J. Graph Theory 14 (1990) 585-597. doi:/10.1002/jgt.3190140510 Zbl0721.05035
  21. [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. [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. [23] H. Wiener, Structural determination of paraffin boiling points, J. Amer. Chem. Soc. 69 (1947) 17-20. doi:10.1021/ja01193a005[Crossref] 
  24. [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. 

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.