## 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 of G is the arithmetic mean of the eccentricities of the vertices of G. It was shown that the average eccentricity of a graph of order n and minimum degree δ cannot exceed [Formula presented], and that this bound is best possible apart from a small additive constant. In this paper we show that for triangle-free graphs this bound can be improved to [Formula presented]. We also show that for graphs not containing a 4-cycle as a subgraph, the bound can be improved to [Formula presented]. We construct graphs to show that the bound for triangle-free graphs is sharp apart from a small additive constant. We also show that the bound for C_{4}-free graphs is close to being best possible by constructing for every value of δ for which δ+1 is a prime power, an infinite sequence of C_{4}-free graphs with average eccentricity at least [Formula presented].

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

Pages (from-to) | 106-114 |

Number of pages | 9 |

Journal | Discrete Applied Mathematics |

Volume | 270 |

DOIs | |

Publication status | Published - 1 Nov 2019 |

## Keywords

- Average eccentricity
- Distance
- Eccentricity
- Minimum degree
- Total eccentricity

## ASJC Scopus subject areas

- Discrete Mathematics and Combinatorics
- Applied Mathematics

## Fingerprint

Dive into the research topics of 'Upper bounds on the average eccentricity of K_{3}-free and C

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