On a relation between the Szeged index and the Wiener index for bipartite graphs

Abstract

{\small The Wiener index $W(G)$ of a graph $G$ is the sum of the distances between all pairs of vertices in the graph. The Szeged index $Sz(G)$ of a graph $G$ is defined as $Sz(G)={\sum }_{e=uv\in E}{n}_u(e)n_v(e)$ where $n_u(e)$ and $n_v(e)$ are, respectively, the number of vertices of $G$ lying closer to vertex $u$ than to vertex $v$ and the number of vertices of $G$ lying closer to vertex $v$ than to vertex $u$. Hansen used the computer programm AutoGraphiX and made the following conjecture about the Szeged index and the Wiener index for a bipartite connected graph $G$ with $n\ge 4$ vertices and $m\ge n$ edges: $$Sz(G)-W(G)\ge 4n-8.$$ Moreover the bound is best possible as shown by the graph composed of a cycle on 4 vertices $C_4$ and a tree $T$ on $n-3$ vertices sharing a single vertex. This paper is to give a confirmative proof to this conjecture.

8 pages

Cited by in corpus (1)

• The (revised) Szeged index and the Wiener index of a nonbipartite graph