Proximity and average eccentricity of a graph

Let G=(V,E)G=(V,E) be a connected graph on n vertices. The proximity  π(G)π(G) of G is the minimum average distance from a vertex of G to all others. The eccentricity  e(v)e(v) of a vertex v in G is the largest distance from v   to another vertex, and the average eccentricity ecc(G)ecc(G) of the graph G   is 1n∑v∈V(G)e(v). Recently, it was conjectured by Aouchiche and Hansen (2011) [3] that for any connected graph G   on n⩾3n⩾3 vertices, ecc(G)−π(G)⩽ecc(Pn)−π(Pn)ecc(G)−π(G)⩽ecc(Pn)−π(Pn), with equality if and only if G≅PnG≅Pn. In this paper, we show that this conjecture is true.

► Two characterizations for a vertex v being a centroidal vertex in a tree are given. ► A kind of transformation for a tree is introduced. ► A conjecture concerning proximity and average eccentricity is proved.