Authors: I. Gutman, X. Li, Y. Mao Title: Inverse problem on the Steiner Wiener index Source: Discussiones Mathematicae Graph Theory Received 16.09.2015, Revised 05.10.2016, Accepted 05.10.2016, doi: 10.7151/dmgt.2000 | |
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_{G}(u,v), where d_{G}(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\/ SW_{k}(G) of G is defined as SW_{k}(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 SW_{k}(G)=w (or SW_{k}(T)=w)? In this paper, we give some solutions to this problem. | |
Keywords: distance, Steiner distance, Wiener index, Steiner Wiener index | |
Links: |