## Abstract

Let G be a finite, connected graph. The eccentricity of a vertex v of G is the distance from v to a vertex farthest from v. The average eccentricity avec(G) of G is the arithmetic mean of the eccentricities of the vertices of G. The Wiener index W(G) of G is the sum of the distances between all unordered pairs of vertices of G. For these two distance measures we give upper bounds in terms of order n, minimum degree δ and maximum degree Δ for graphs of girth at least six, and for graphs containing neither 4-cycles nor 5-cycles as subgraphs. For graphs of girth at least six we show that the average eccentricity is bounded above by [Formula presented], where Δ^{∗}=Δδ+(δ−1)Δ(δ−2)+[Formula presented]. We construct graphs that show that for δ−1 a prime power this bound is sharp apart from a term O(Δ). We further show that if the girth condition on G is relaxed to G having neither a 4-cycle nor a 5-cycle as a subgraph, then similar and only slightly weaker bounds hold. For such graphs we also show that the average eccentricity is bounded from above by [Formula presented]⌈[Formula presented]⌉+8, which in some sense is close to being optimal. We obtain similar upper bounds for the Wiener index of graphs of girth at least 6 and for graphs containing neither a 4-cycle nor a 5-cycle as a subgraph.

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

Pages (from-to) | 98-111 |

Number of pages | 14 |

Journal | Discrete Applied Mathematics |

Volume | 330 |

DOIs | |

Publication status | Published - 15 May 2023 |

## Keywords

- Average distance
- Average eccentricity
- Girth
- Maximum degree
- Minimum degree
- Total eccentricity
- Wiener index

## ASJC Scopus subject areas

- Discrete Mathematics and Combinatorics
- Applied Mathematics

## Fingerprint

Dive into the research topics of 'On Wiener index and average eccentricity of graphs of girth at least 6 and (C_{4},C

_{5})-free graphs'. Together they form a unique fingerprint.