## 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. In this paper we show that the well-known upper bound (_{δ+1}^{n} + 2)(^{n}_{2}) on the Wiener index of a graph of order n and minimum degree δ [M. Kouider, P. Winkler, Mean distance and minimum degree. J. Graph Theory 25 no. 1 (1997)] can be improved significantly if the graph contains also a vertex of large degree. Specifically, we give the asymptotically sharp bound W(G) ≤ ^{(n-∆+}_{2}^{δ)n}_{δ}^{+2∆}_{+1} + 2n(n - 1) on the Wiener index W(G) of a graph G of order n, minimum degree δ and maximum degree ∆. We prove a similar result for triangle-free graphs, and we determine a bound on the Wiener index of C4-free graphs of given order, minimum and maximum degree and show that it is, in some sense, best possible.

Original language | English |
---|---|

Journal | Discrete Mathematics and Theoretical Computer Science |

Volume | 23 |

Issue number | 1 |

DOIs | |

Publication status | Published - 2021 |

## Keywords

- Average distance
- Maximum degree
- Mean distance
- Minimum degree MSC-class: 05C12
- Total distance
- Wiener index

## ASJC Scopus subject areas

- Theoretical Computer Science
- General Computer Science
- Discrete Mathematics and Combinatorics