The Nordhaus–Gaddum-type inequality for the Wiener polarity index

Yanhong Zhang and Yumei Hu

Applied Mathematics and Computation, 2016, vol. 273, issue C, 880-884

Abstract: The Wiener polarity index Wp(G) of a graph G is the number of unordered pairs of vertices {u, v} of G such that the distance between u and v is 3. In this paper, we study the Nordhaus–Gaddum-type inequality for the Wiener polarity index of a graph G of order n. Due to concerns that both Wp(G) and Wp(G¯) are nontrivial only when diam(G)=3 and diam(G¯)=3, we firstly consider the crucial case and get that 2≤Wp(G)+Wp(G¯)≤⌈n2⌉⌊n2⌋−n+2. Moreover, the bounds are best possible, and the corresponding extremal graphs are also presented. Then we generalize the results to all connected simple graphs. Furthermore, we discuss the Nordhaus–Gaddum-type inequality for trees and unicyclic graphs, respectively.

Keywords: The Wiener polarity index; Diameter; Complement; Extremal graph; Nordhaus–Gaddum-type inequality (search for similar items in EconPapers)
Date: 2016
References: View complete reference list from CitEc
Citations: View citations in EconPapers (6)

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S009630031501396X
Full text for ScienceDirect subscribers only

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:eee:apmaco:v:273:y:2016:i:c:p:880-884

DOI: 10.1016/j.amc.2015.10.045

Access Statistics for this article

Applied Mathematics and Computation is currently edited by Theodore Simos

More articles in Applied Mathematics and Computation from Elsevier
Bibliographic data for series maintained by Catherine Liu ().