Average eccentricity, minimum degree and maximum degree in graphs

摘要

Let G be a connected finite graph with vertex set V(G). The eccentricity e(v) of a vertex v is the distance from v to a vertex farthest from v. The average eccentricity of G is defined as 1 /vertical bar V(G)vertical bar Sigma(v is an element of V(G)) e(v). We show that the average eccentricity of a connected graph of order n, minimum degree delta and maximum degree Delta does not exceed 9/4 n-Delta-1/delta+1 (1 + Delta-delta/3n) + 7, and this bound is sharp apart from an additive constant. We give improved bounds for triangle-free graphs and for graphs not containing 4-cycles.