给定点数,最小度和条件直径的图的边数的上界∗
2021-07-24马花萍田应智
马花萍,田应智
(新疆大学 数学与系统科学学院,新疆 乌鲁木齐 830046)
0 引言
本文中没有定义的图论术语和符号,请参考文献[1],在这篇文章中主要研究的是有限简单图.设G 是一个顶点集为V(G),边集为E(G)的图,图G 的阶n=|V(G)|为其顶点的数目,m=|V(G)|为其边的数目.对于V(G)中的每一个点v ∈V(G),NG(v)表示与点v 相邻的所有的顶点的集合,用NG(v)表示v 的邻点集,并且dG(v)=|NG(v)|称为图G 中点v 的度数.用δ(G)表示图G 的最小度.对于两个不交的点子集V1和V2,[V1,V2]G表示图G中所有边的集合,连接了点集V1和V2中的点.取任意数x,其中x表示x 取上整数,即为不小于x的最小整数,x表示x 取下整数,即为不超过x 的最大整数.
任意两个点u 和v 之间的距离dG(u,v)定义为图G 中从点u 到v 的最短路的长度.对于连通图G,定义其直径D(G)为max{dG(u,v):u,v ∈V(G)},如果图G 不连通,则D(G)=∞.设V1⊆V(G)和V2⊆V(G) 是V(G)的两个非空点子集,用d(V1,V2)表示u ∈V1和v ∈V2之间的最短距离dG(u,v).为减少歧义,本文用N(v),d(v),[V1,V2],d(u,v)和d(V1,V2)表示NG(v),dG(v),[V1,V2]G,dG(u,v)和dG(V1,V2).
Balbuena等人在文献[2]中推广了直径,介绍了图G 的条件直径,给定条件P 使得V(G)中至少有一对非空点子集(V1,V2)满足给定的条件P,条件直径DP(G)定义为max{dG(V1,V2):∅/=V1,V2⊆V(G),其中(V1,V2) 满足条件P}.由于条件直径是测量具有给定条件的顶点子集之间的最大距离,因此它们可以用于某些需要控制特定网络群集之间的通信延迟.
设l 和s 是两个整数且满足1 ≤s ≤l.考虑P 满足下面条件:(Vl,Vs)⊆V(G)×V(G)满足P 当且仅当|Vl|=l和|Vs|=s.在这种情况下,文献[3]中用D(G;l,s)来表示条件直径DP(G),即

注意到D(G;1,1)恰好为图的直径D(G),并且当D(G;l,s)=0 时当且仅当l+s>|V(G)|.同时当l+s ≤|V(G)|时有D(G;l,s)≤|V(G)|+1−(l+s).
给定点数,最大度和直径条件下图的边数下界是由Erd˝os和R´enyi在文献[4]以及Erd˝os,R´enyi和S´os在文献[5]中给出的.给定……