Extremal Problem on Diameter and Average Distance of Graphs
Xu Jun · 2004
The diameter and average distance of a graph are two important parameters for measuring the efficiency of interconnection networks. In the present paper, we investigate the constraint relationship among diameter, average distance, order and size of a graph. Considering that any graph can be obtained by removing some edges from a complete graph, a short proof and a counterpart for a digraph of Ore's result is given. Using a similar method, a lower bound on average distance of a graph with diameter is given, and combining this result with Ore's yields a new lower bound dependent only on the order and diameter, which is better than Plesnik's.