# New bounds on the average eccentricity of graphs

###
Peter Dankelmann

University of Johannesburg

PDF

**Minisymposium:**
GENERAL SESSION TALKS

**Content:**
Let $G$ be a connected graph of order $n$. The {\it eccentricity}
${\rm ecc}(v)$ of a vertex $v$ of $G$ is the distance from
$v$ to a vertex farthest from $v$, i.e.,
${\rm ecc}(v) = \max_{w\in V(G)} d(v,w)$, where $V(G)$ is the
vertex set of $G$ and $d(v,w)$ denotes the distance between
$v$ and $w$ in $G$.
The {\it average eccentricity} ${\rm avec}(G)$ of $G$ is the arithmetic
mean of the eccentricities of all vertices of $G$, i.e.,
\[ {\rm avec}(G) = \frac{1}{n} \sum_{v\in V(G)} {\rm ecc}(v). \]
The average eccentricity, originally conceived as a performance
indicator for transportation networks, has also attracted much
interest within graph theory. Several recent results on
the average eccentricity have been inspired by conjectures of the
computer programme AutoGraphiX.
In this talk we give sharp bounds on the average eccentricity
in terms of other graph parameters, in particular chromatic number,
domination number, connected domination number and independence number.
We also present bounds on the average eccentricity for graphs of given
order and size, and for planar and maximal planar graphs. Our bounds
are best possible, except for additive constants.