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

详细信息    查看全文

• 作者：Yaping Mao^a ; ^{maoyaping@ymail.com} ; Zhao Wang^a ; ^b ; ^{wangzhao380@yahoo.com} ; Ivan Gutman^c ; ^d ; ^{gutman@kg.ac.rs} ; He Li^a ; ^{lihe0520@yahoo.com}
• 关键词：Distance (in graph) ; Steiner distance ; Wiener index ; Steiner Wiener index ; Nordhaus&ndash ; Gaddum relations
• 刊名：Discrete Applied Mathematics
• 出版年：2017
• 出版时间：11 March 2017
• 年：2017
• 卷：219
• 期：Complete
• 页码：167-175
• 全文大小：432 K
• 卷排序：219

文摘

The Wiener index WW of a connected graph GG with vertex set V(G)V(G) is defined as W=∑u,v∈V(G)d(u,v)W=∑u,v∈V(G)d(u,v) where d(u,v)d(u,v) stands for the distance between the vertices uu and vv of GG. For S⊆V(G)S⊆V(G), the Steiner distance d(S)d(S) of the vertices of SS is the minimum size of a connected subgraph of GG whose vertex set contains SS. The kkth Steiner Wiener index SWk(G)SWk(G) of GG is defined as the sum of Steiner distances of all kk-element subsets of V(G)V(G). In 2005, Zhang and Wu studied the Nordhaus–Gaddum problem for the Wiener index. We now obtain analogous results for SWkSWk, namely sharp upper and lower bounds for SWk(G)+SWk(G¯) and SWk(G)⋅SWk(G¯), valid for any connected graph GG whose complement G¯ is also connected.