Average Distance of Neighbourhood Graphs

The average distance m(G) of a connected graph G of order n is the average of the distances between all pairs of vertices of G. The eccentricity, ecG(v), of a vertex v 2 V(G) is the maximum distance between v and any other vertex in G. The minimum eccentricity of G is the radius of G, denoted by rad(G). The neighbourhood graph of G, denoted by G0 is the graph with the same vertex set as G in which two vertices are adjacent if and only if they have a common neighbour in G. We show that rad(G0) <= rad(G) and m(G0)<=  m(G). Moreover, we determine graphs for which the bounds are best possible.

Keywords: Radius, Average distance, Neighbourhood graph, Bipartite graph