An inequality between the edge-Wiener index and the Wiener index of a graph

Martin Knor, Riste Škrekovski and Aleksandra Tepeh

Applied Mathematics and Computation, 2015, vol. 269, issue C, 714-721

Abstract: The Wiener index W(G) of a connected graph G is defined to be the sum ∑u, vd(u, v) of distances between all unordered pairs of vertices in G. Similarly, the edge-Wiener index We(G) of G is defined to be the sum ∑e, fd(e, f) of distances between all unordered pairs of edges in G, or equivalently, the Wiener index of the line graph L(G). Wu (2010) showed that We(G) ≥ W(G) for graphs of minimum degree 2, where equality holds only when G is a cycle. Similarly, in Knor et al. (2014), it was shown that We(G)≥δ2−14W(G) where δ denotes the minimum degree in G. In this paper, we extend/improve these two results by showing that We(G)≥δ24W(G) with equality satisfied only if G is a path on 3 vertices or a cycle. Besides this, we also consider the upper bound for We(G) as well as the ratio We(G)W(G). We show that among graphs G on n vertices We(G)W(G) attains its minimum for the star.

Keywords: Wiener index; Gutman index; Line graph (search for similar items in EconPapers)
Date: 2015
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (4)

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0096300315009698
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:269:y:2015:i:c:p:714-721

DOI: 10.1016/j.amc.2015.07.050

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 ().