Wiener index in graphs given girth, minimum, and maximum degrees
Open Access
- 1 January 2023
- journal article
- Published by Georgia Southern University in Theory and Applications of Graphs
- Vol. 10 (2) , 1-18
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
This publication has 10 references indexed in Scilit:
- On Wiener index and average eccentricity of graphs of girth at least 6 and -free graphsDiscrete Applied Mathematics, 2023
- The average eccentricity of a graph with prescribed girthDiscrete Mathematics, 2022
- Radius, girth and minimum degreeJournal of Graph Theory, 2022
- Distances in graphs of girth 6 and generalised cagesDiscrete Applied Mathematics, 2021
- Average eccentricity, minimum degree and maximum degree in graphsJournal of Combinatorial Optimization, 2020
- Average Distance, Independence Number, and Spanning TreesJournal of Graph Theory, 2013
- The Steiner diameter of a graph with prescribed girthDiscrete Mathematics, 2013
- The extremal values of the Wiener index of a tree with given degree sequenceDiscrete Applied Mathematics, 2008
- Average distance, minimum degree, and spanning treesJournal of Graph Theory, 2000
- On the sum of all distances in a graph or digraphJournal of Graph Theory, 1984