关于图的直径和平均距离

图的直径和平均距离是度量网络有效性的两个重要参数．Ore通过图的顶点数和直径给出无向图的最大边数．Entringer，Jakson，Slater和Ng，Teh通过图的顶点数和边数分别给出无向图和有向图平均距离的下界．该文提供这两个结果的简单证明，给出有向图类似Ore的结果，并通过图的直径改进Entringer等人的结果到更一般的情形．结合本文和Ore的结果，可以得到一个无向图和有向图平均距离的下界，它比Plesnik得到的下界更好．

On Diameter and Average Distance of Graphs

The diameter and average distance of a graph are two important parameters to measure the efficiency 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.