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 (δ+1n + 2)(n2) 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