Steiner Wiener index of graph products

Document Type : Research Paper

Authors

1 Department of Mathematics, Qinghai Normal University

2 School of Mathematical Sciences, Beijing Normal Universit

3 University of Kragujevac Kragujevac, Serbia

Abstract

The Wiener index $W(G)$ of a connected graph $G$‎ ‎is defined as $W(G)=\sum_{u,v\in V(G)}d_G(u,v)$‎ ‎where $d_G(u,v)$ is the distance between the vertices $u$ and $v$ of‎ ‎$G$‎. ‎For $S\subseteq V(G)$‎, ‎the Steiner distance $d(S)$ of‎ ‎the vertices of $S$ is the minimum size of a connected subgraph of‎ ‎$G$ whose vertex set is $S$‎. ‎The  $k$-th Steiner Wiener index‎ ‎$SW_k(G)$ of $G$ is defined as‎ ‎$SW_k(G)=\sum_{\overset{S\subseteq V(G)}{|S|=k}} d(S)$‎. ‎We establish‎ ‎expressions for the $k$-th Steiner Wiener index on the join‎, ‎corona‎, ‎cluster‎, ‎lexicographical product‎, ‎and Cartesian product of graphs‎.

Keywords

Main Subjects


[1] J. A. Bondy and U. S. R. Murty, Graph theory, Springer, New York, 2008.

[2] F. Buckley and F. Harary, Distance in graphs, Addison–Wesley, Redwood, 1990.

[3] J. Cáceresa, A. Márquezb and M. L. Puertasa, Steiner distance and convexity in graphs, Eur. J. Combin., 29 (2008) 726–736.

[4] G. Chartrand, O. R. Oellermann, S. Tian and H. B. Zou, Steiner distance in graphs, Casopis Pest. Mat., 114 (1989) 399–410.

[5] P. Dankelmann, O. R. Oellermann and H. C. Swart, The average Steiner distance of a graph, J. Graph Theory, 22 (1996) 15–22.

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

[7] A. Dobrynin, R. Entringer and I. Gutman, Wiener index of trees: theory and application, Acta Appl. Math., 66 (2001) 211–249.

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

[9] I. Gutman and B. Furtula (Eds.), Distance in molecular graphs – theory, Univ. Kragujevac, Kragujevac, 2012.
[10] I. Gutman and B. Furtula (Eds.), Distance in molecular graphs – applications, Univ. Kragujevac, Kragujevac, 2012.

[11] I. Gutman, B. Furtula and X. Li, Multicenter Wiener indices and their applications, J. Serb. Chem. Soc., in press; doi: 10.2298/JSC150126015G.

[12] X. Li, Y. Mao and I. Gutman, The Steiner Wiener index of a graph, Discuss. Math. Graph Theory, 36 no. 2 (2016) 455–465.

[13] Y. Mao and E. Cheng, Steiner distance in product networks, submitted.

[14] D. H. Rouvray and R. B. King (Eds.), Topology in chemistry – discrete mathematics of molecules, Horwood, Chich-ester, 2002.

[15] H. Wiener, Structural determination of paraffin boiling points, J. Am. Chem. Soc., 69 (1947) 17–20.

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

[17] Y. Yeh and I. Gutman, On the sum of all distances in composite graphs,Discrete Math., 135 (1994) 359–365.