TY - JOUR
T1 - Nordhaus-Gaddum-type inequality for the hyper-Wiener index of graphs when decomposing into three parts
AU - Su, Guifu
AU - Xiong, Liming
AU - Sun, Yi
AU - Li, Daobin
PY - 2013/2/3
Y1 - 2013/2/3
N2 - Let k≥2 be an integer, a k-decomposition(G1, G2,⋯,Gk) of a graph G is a partition of its edge set to form k spanning subgraphs G1,G2,.,Gk. The hyper-Wiener index WW is one of the recently conceived distance-based graph invariants (Randi 1993 [15]): WW=WW(G):=12W(G)+12W2(G), where W is the Wiener index (Wiener 1947 [18]) and W2 is the sum of squares of distance of all pairs of vertices in G. In this paper, we investigate the Nordhaus-Gaddum-type inequality of a 3-decomposition of Kn for the hyper-Wiener index: 7n2≤WW(G1)+WW(G2)+WW( G3)≤2n+24+n2+4(n-1). The corresponding extremal graphs are characterized.
AB - Let k≥2 be an integer, a k-decomposition(G1, G2,⋯,Gk) of a graph G is a partition of its edge set to form k spanning subgraphs G1,G2,.,Gk. The hyper-Wiener index WW is one of the recently conceived distance-based graph invariants (Randi 1993 [15]): WW=WW(G):=12W(G)+12W2(G), where W is the Wiener index (Wiener 1947 [18]) and W2 is the sum of squares of distance of all pairs of vertices in G. In this paper, we investigate the Nordhaus-Gaddum-type inequality of a 3-decomposition of Kn for the hyper-Wiener index: 7n2≤WW(G1)+WW(G2)+WW( G3)≤2n+24+n2+4(n-1). The corresponding extremal graphs are characterized.
KW - Hyper-Wiener index
KW - Nordhaus-Gaddum-type inequality
KW - Wiener index
KW - k-decomposition
UR - http://www.scopus.com/inward/record.url?scp=84872370086&partnerID=8YFLogxK
U2 - 10.1016/j.tcs.2012.10.049
DO - 10.1016/j.tcs.2012.10.049
M3 - Article
AN - SCOPUS:84872370086
SN - 0304-3975
VL - 471
SP - 74
EP - 83
JO - Theoretical Computer Science
JF - Theoretical Computer Science
ER -