Research ArticleNo Access

Wiener index and Steiner 3-Wiener index of graphs

Matjaž Kovše

School of Basic Sciences, IIT Bhubaneswar, India

E-mail Address: matjaz.kovse@gmail.com

Search for more papers by this author

V. A. Rasila

Department of Mathematics, Cochin University of Science and Technology, India

E-mail Address: 17rasila17@gmail.com

Corresponding author.

Search for more papers by this author

, and

Ambat Vijayakumar

Department of Mathematics, Cochin University of Science and Technology, India

E-mail Address: vambat@gmail.com

Search for more papers by this author

https://doi.org/10.1142/S1793557121501655Cited by:2 (Source: Crossref)

Abstract

Let $S$ be a set of vertices of a connected graph $G$ . The Steiner distance of $S$ is the minimum size of a connected subgraph of $G$ containing all the vertices of $S$ . The sum of all Steiner distances on sets of size $k$ is called the Steiner $k$ -Wiener index. A graph $G$ is modular if for every three vertices $x, y, z$ there exists a vertex $w$ that lies on the shortest path between every two vertices of $x, y, z$ . The Steiner 3-Wiener index of a modular graph is obtained in terms of its Wiener index. As concrete examples, we discuss the case of Fibonacci, Lucas cubes and the Cartesian product of modular graphs. The Steiner Wiener index of block graphs is also studied.

Communicated by H. Tanaka

Keywords:

AMSC: 05C09, 05C12

References

1. H. J. Bandelt, A. Dählmann and H. Schütte, Absolute retracts of bipartite graphs, Discrete Appl. Math. 16 (1987) 191–215. Crossref, Web of Science, Google Scholar
2. R. B. Bapat and S. Sivasubramanian, Inverse of the distance matrix of a block graph, Linear and Multilinear Algebra 59 (2011) 1393–1397. Crossref, Web of Science, Google Scholar
3. A. Behtoei, J. Mohsen and T. Bijan, A characterization of block graphs, Discrete Appl. Math. 158 (2010) 219–221. Crossref, Web of Science, Google Scholar
4. G. Chartrand, O. R. Oellermann, S. L. Tian and H. B. Zou, Steiner distance in graphs, Časopis pro pěstování matematiky 114 (1989) 399–410. Google Scholar
5. P. Dankelmann, O. R. Oellermann and H. C. Swart, The average Steiner distance of a graph, J. Graph Theory 22 (1996) 15–22. Crossref, Web of Science, Google Scholar
6. A. Graovac and T. Pisanski, On the Wiener index of a graph, J. Math. Chem. 8 (1991) 53–62. Crossref, Web of Science, Google Scholar
7. S. Klavžar, Structure of Fibonacci cubes: A survey, J. Comb. Optim. 25 (2013) 505–522. Crossref, Web of Science, Google Scholar
8. S. Klavžar and M. Mollard, Wiener index and Hosoya polynomial of Fibonacci and Lucas cubes, MATCH Commun. Math. Comput. Chem. 68 (2012) 311–324. Web of Science, Google Scholar
9. T. Koshy, Fibonacci and Lucas Numbers with Applications (John Wiley and Sons, 2019). Google Scholar
10. M. Kovše, V. A. Rasila and A. Vijayakumar, Steiner Wiener index of block graphs, AKCE Int. J. Graphs Comb. 17(3) (2020) 833–840. Crossref, Web of Science, Google Scholar
11. E. Kubicka, G. Kubicki and O. R. Oellermann, Steiner intervals in graphs, Discrete Appl. Math. 81 (1998) 181–190. Crossref, Web of Science, Google Scholar
12. X. Li, Y. Mao and I. Gutman, The Steiner Wiener index of a graph, Discuss. Math. Graph Theory 36 (2016) 455–465. Crossref, Web of Science, Google Scholar
13. Y. Mao, Steiner distance in graphs — A survey, preprint (2017), arXiv:1708.05779 [math.CO]. Google Scholar
14. Y. Mao, Z. Wang and I. Gutman, Steiner Wiener index of graph products, Trans. Combin. 5(3) (2016) 39–50. Web of Science, Google Scholar
15. H. Wiener, Structural determination of paraffin boiling points, J. Am. Chem. Soc. 69 (1947) 17–20. Crossref, Web of Science, Google Scholar
16. H. G. Yeh, C. Y. Chiang and S. H. Peng, Steiner centers and Steiner medians of graphs, Discrete Math. 308 (2008) 5298–5307. Crossref, Web of Science, Google Scholar
17. Y. Yeh and I. Gutman, On the sum of all distances in composite graphs, Discrete Math. 135 (1994) 359–365. Crossref, Web of Science, Google Scholar