Steiner Wiener Index of Complete m-Ary Trees

Document Type : Review Article


Department of mathematics, Faculty of natural and computational science, Woldia University, Woldia, Ethiopia


Let $G$ be a connected graph with vertex set $V(G)$ and edge set $E(G)$. For a subset $S$ of $V(G)$, the Steiner distance $d(S)$ of $S$ is the minimum size of a connected subgraph whose vertex
set contains $S$. For an integer $k$ with $2 \le k \le n - 1$, the $k$-th Steiner Wiener index of a graph $G$ is defined as
$SW_k(G) = \sum_{\substack{S\subseteq V(G)\\ |S|=k}}d(S)$. In this paper, we present exact values of the $k$-th Steiner Wiener index of complete $m$-ary trees by using inclusion-excluision principle for various values of $k$.


  1. 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.
  2. R. C. Entringer, D. E. Jackson and D. A. Snyder, Distance in graphs, Czechoslovak Math. J. 26 (1976) 283 296.
  3. A. Dobrynin, R. Entringer and I. Gutman, Wiener index of trees: theory and application, Acta Appl. Math. 66 (2001) 211 249.
  4. M. Ghorbani, X. Li, H. R. Maimani, Y. Mao, S. Rahmani and M. Rajabi-Parsa, Steiner (revised) Szeged index of graphs, MATCH Commun. Math. Comput. Chem. 82 (2019) 733 742.
  5. I. Gutman, S. Klavžar and B. Mohar, Fifty years of the Wiener index, MATCH Commun. Math. Comput. Chem. 35 (1997) 1 159.
  6. I. Gutman and O. E. Polansky, Mathematical Concepts in Organic Chemistry, Springer, Berlin-Heidelberg-New York-Tokyo, 1986.
  7. Y. L. Jin and X. D. Zhang, On two conjectures of the Wiener index, MATCH Commun. Math. Comput. Chem. 70 (2013) 583 589.
  8. S. Klavžar and M. J. Nadjafi-Arani, Wiener index in weighted graphs via unification of - classes, European J. Combin. 36 (2014) 71 76.
  9. M. Knor and R. Škrekovski, Wiener index of generalized 4-stars and of their quadratic line graphs, Australas. J. Combin. 58 (2014) 119 126.
  10.  X. Li and M. Zhang, Results on two kinds of Steiner distance-based indices for some classes of graphs, MATCH Commun. Math. Comput. Chem. 84 (2020) 567 578.
  11.  Y. Mao, Z. Wang and I. Gutman, Steiner Wiener index of graph products, Trans. Comb. 5 (2016) 39-50.
  12.  Y. Mao, Z. Wang, I. Gutman and A. Klobučar, Steiner degree distance, MATCH Commun. Math. Comput. Chem. 78 (2017) 221 230.
  13.  M. Masre, S. A. Fufa and T. Vetrík, Distance-based indices of complete m-ary trees, Discrete Math. Algorithms Appl. 12 (4) (2020) 2050041.
  14.  H. Wiener, Structural determination of paraffin boiling points, J. Amer. Chem. Soc. 69 (1947) 17 20.
  15. 15.  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.