Nordhaus-Gaddum-type inequality for the hyper-Wiener index of graphs when decomposing into three parts

Guifu Su; Liming Xiong; Yi Sun; Daobin Li

doi:10.1016/j.tcs.2012.10.049

Nordhaus-Gaddum-type inequality for the hyper-Wiener index of graphs when decomposing into three parts

Guifu Su^*
, Liming Xiong
, Yi Sun
, Daobin Li

^*Corresponding author for this work

School of Mathematics and Statistics

Beijing Institute of Technology
Jiangxi University
Xinjiang University
University of Science and Technology Beijing

Research output: Contribution to journal › Article › peer-review

2 Citations (Scopus)

Abstract

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)+12^W2(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.

Original language	English
Pages (from-to)	74-83
Number of pages	10
Journal	Theoretical Computer Science
Volume	471
DOIs	https://doi.org/10.1016/j.tcs.2012.10.049
Publication status	Published - 3 Feb 2013

Keywords

Hyper-Wiener index
Nordhaus-Gaddum-type inequality
Wiener index
k-decomposition

Access to Document

10.1016/j.tcs.2012.10.049

Cite this

@article{c72b91593c7f4f23b2ed4e42a4408d8e,

title = "Nordhaus-Gaddum-type inequality for the hyper-Wiener index of graphs when decomposing into three parts",

abstract = "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.",

keywords = "Hyper-Wiener index, Nordhaus-Gaddum-type inequality, Wiener index, k-decomposition",

author = "Guifu Su and Liming Xiong and Yi Sun and Daobin Li",

year = "2013",

month = feb,

day = "3",

doi = "10.1016/j.tcs.2012.10.049",

language = "English",

volume = "471",

pages = "74--83",

journal = "Theoretical Computer Science",

issn = "0304-3975",

publisher = "Elsevier B.V.",

}

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 - https://www.scopus.com/pages/publications/84872370086

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 -

Nordhaus-Gaddum-type inequality for the hyper-Wiener index of graphs when decomposing into three parts

Abstract

Keywords

Access to Document

Other files and links

Fingerprint

Cite this