Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
4949735 | Discrete Applied Mathematics | 2017 | 9 Pages |
Abstract
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.
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Yaping Mao, Zhao Wang, Ivan Gutman, He Li,