I. Gutman, X. Li, Y. Mao
Inverse problem on the Steiner Wiener index
Discussiones Mathematicae Graph Theory
Received 16.09.2015, Revised 05.10.2016, Accepted 05.10.2016, doi: 10.7151/dmgt.2000

The Wiener index W(G) of a connected graph G, introduced by Wiener in 1947, is defined as W(G)=∑u,v∈V(G)dG(u,v), where dG(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\/ SWk(G) of G is defined as SWk(G)=∑\overset{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 SWk(G)=w (or SWk(T)=w)? In this paper, we give some solutions to this problem.
distance, Steiner distance, Wiener index, Steiner Wiener index