Nordhaus-Gaddum-type results for the Steiner Wiener index of graphs

The Wiener index W of a connected graph G with vertex set V(G) is defined as W=∑u,v∈V(G)d(u,v) where d(u,v) stands for the distance between the vertices u and v of G. For S⊆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 contains S. The kth Steiner Wiener index SWk(G) of G is defined as the sum of Steiner distances of all k-element subsets of V(G). In 2005, Zhang and Wu studied the Nordhaus-Gaddum problem for the Wiener index. We now obtain analogous results for SWk, namely sharp upper and lower bounds for SWk(G)+SWk(G¯) and SWk(G)⋅SWk(G¯), valid for any connected graph G whose complement G¯ is also connected.