Wiener index in graphs given girth, minimum, and maximum degrees

Abstract

Let $G$ be a connected graph of order $n$. The Wiener index $W(G)$ of $G$ is the sum of the distances between all unordered pairs of vertices of $G$. The well-known upper bound $\big( \frac{n}{\delta+1}+2\big) {n \choose 2}$ on the Wiener index of a graph of order $n$ and minimum degree $\delta$ by Kouider and Winkler \cite{Kouider} was improved significantly by Alochukwu and Dankelmann \cite{Alex} for graphs containing a vertex of large degree $\Delta$ to $W(G) \leq {n-\Delta+\delta \choose 2} \big( \frac{n+2\Delta}{\delta+1}+4 \big)$. In this paper, we give upper bounds on the Wiener index of $G$ in terms of order $n$ and girth $g$, where $n$ is a function of both the minimum degree $\delta$ and maximum degree $\Delta$. Our result provides a generalisation for these previous bounds for any graph of girth $g$. In addition, we construct graphs to show that, if for given $g$, there exists a Moore graph of minimum degree $\delta$, maximum degree $\Delta$ and girth $g$, then the bounds are asymptotically sharp.

Keywords

• wiener index
• average distance
• girth
• minimum degree
• maximum degree