On Diameter and Average Distance of Graphs
Tao Zhou, Jun‐Ming Xu, Liu Jun · 2004
The diameter and average distance of a graph are two important parameters to measure the eciency of interconnection networks. Ore gave an upper bound of the number of edges of an undirected graph in terms of order and diameter of the graph. Entringer et at gave a lower bound of the average distance of an undirected graph and, respectively, a digraph in terms of order and the number of edges of the graph. The present paper provides short proofs of these two results and gives a counterpart of Ore’s result for a digraph, and improves Entringer et al’s results in term of diameter of the graph. Combining our results with Ore’s will yield a new lower bound on (G) better than that given by Plesnik.