New bounds on the average eccentricity of graphs

Peter Dankelmann
University of Johannesburg



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.

Back to all abstracts