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.

Back to all abstracts