Proximity and average eccentricity of a graph
Let G = (V, E) be a connected graph on n vertices. The proximity pi(G) of G is the minimum average distance from a vertex of G to all others. The eccentricity e(nu) of a vertex nu in G is the largest distance from nu to another vertex, and the average eccentricity ecc(G) of the graph G is 1/n Sigma(nu is an element of V(G)) e(nu). Recently, it was conjectured by Aouchiche and Hansen (2011) [3] that for any connected graph G on n >= 3 vertices, ecc(G) - pi(G) <= ecc(P-n) - pi(P-n), with equality if and only if G congruent to P-n. In this paper, we show that this conjecture is true. (C) 2012 Elsevier B.V. All rights reserved.
proximity average eccentricity eccentricity combinatorial problems