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

Research output: Contribution to journalArticlepeer-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)+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.

Original languageEnglish
Pages (from-to)74-83
Number of pages10
JournalTheoretical Computer Science
Volume471
DOIs
Publication statusPublished - 3 Feb 2013

Keywords

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

Fingerprint

Dive into the research topics of 'Nordhaus-Gaddum-type inequality for the hyper-Wiener index of graphs when decomposing into three parts'. Together they form a unique fingerprint.

Cite this