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

###
Aleksandra Tepeh

FEECS, University of Maribor and FIŠ, Novo mesto

####
Martin Knor

STU, Bratislava

####
Riste Škrekovski

FIŠ, FMF, FAMNIT, IMFM

PDF

**Minisymposium:**
CHEMICAL GRAPH THEORY

**Content:**
The Wiener index $W(G)$ of a connected graph $G$ is defined to be
the sum $\sum_{u,v} d(u,v)$ of distances between all unordered pairs
of vertices in $G$. Similarly, the edge-Wiener index $W_e(G)$ of $G$
is defined to be the sum $\sum_{e,f} d(e,f)$ of distances between
all unordered pairs of edges in $G$, or equivalently, the Wiener
index of the line graph $L(G)$. Wu showed that $W_e(G) \ge
W(G)$ for graphs of minimum degree $2$, where equality holds only
when $G$ is a cycle. Similarly, Knor, Poto\v cnik, \v Skrekovski showed that
$W_e(G) \ge \frac{\delta^2-1}{4} W(G)$ where $\delta$ denotes the
minimum degree in $G$. In this talk, we extend/improve these two
results by showing that $W_e(G) \ge \frac{\delta^2}{4} W(G)$ with
equality satisfied only if $G$ is a path on 3 vertices or a cycle.
In addition, we show that among graphs $G$ on $n$ vertices
$\frac{W_e(G)}{W(G)}$ attains its minimum for the star.