给定点数,最小度和条件直径的图的边数的上界

On Size,Order,Minimum Degree and Conditional Diameter of Graphs

图G的直径是G中任意两个点之间的最大距离.给定两个正整数l和s,条件直径D(G;l,s)是点数分别为l和s的两个点集之间的最大距离.当l=s=1时,图G的条件直径D(G;1,1)恰好是图G的直径D(G).本文得到了在给定点数,最小度和条件直径下图G的边数上界,且验证了这个边数的上界是渐进紧的.

The diameter D(G)of a graph G is the the maximum distance between two vertices in G.For given positive integers l and s,the conditional diameter D(G;l,s)of a graph G is the maximum distance between two subsets of vertices with cardinalities l and s.When l=s=1,the conditional diameter D(G;1,1)is just the diameter D(G)of G.In this paper,we obtain an asymptotically tight upper bound on the size of G in terms of order,minimum degree and conditional diameter.