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

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

作　　者：马花萍 田应智[1] MA Huaping;TIAN Yingzhi(School of Mathematics and System Sciences,Xinjiang University,Urumqi Xinjiang 830046,China)

机构地区：[1]新疆大学数学与系统科学学院,新疆乌鲁木齐830046

出　　处：《新疆大学学报（自然科学版）（中英文）》2021年第4期385-396,共12页Journal of Xinjiang University(Natural Science Edition in Chinese and English)

基　　金：国家自然科学基金(11861066,11531011);新疆天山青年项目(2018Q066).

摘　　要：图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.

关 键 词：直径 条件直径 最小度 

分 类 号：O175[理学—数学]