设G是无向简单连通图,A和B是G的两个不相交的顶点子集,定义[A,B]为一个端点在A中,另一个端点在B中的边所成的集合.s=[X,Y]称为G的边割,其中X∈V(G),Y=V(G)\X.设k是正整数,若G-s的每个连通分支都至少有k个点,则称s是G的一个k-限制边割.若G存在k-限制边割,则称G为λk-连通图.G的最小k-限制边割所含的边数称为G的k-限制边连通度,记为λk(G).令ζk(G)=min{|[X,X]|：X∈V(G),|X|=k,G[X]连通},其中X=V(G)\X.若λk(G)=ζk(G),则称G是λk-最优的.若G的每个最小k-限制边割都能分离一个k阶连通子图,则称G是超级-λk的.本文主要研究图的k-限制边连通性的最优化问题,共分为四章.第一章主要介绍一些本文将要用到的图论方面的基本概念.第二章给出图是λ5-最优和超级的邻域交条件.主要结果如下：(1)设G是阶至少为21的λ5-连通图.若对G中任意一对不相邻的顶点u和v都有|N(u)∩N(v)|≥5,且ζ5(G)≤[v/2]+10,则除一类特殊图外,G是A5-最优的.(2)设G是阶至少为21的λ5-连通图.若对G中任意一对不相邻的顶点u和v都有|N(u)∩N(v)|≥6,且ξ5(G)≤[v/2]+11,则G是超级-λ5的.第三章给出图是λ5-最优和超级的度条件.主要结果如下：(1)设G是阶至少为21的λ5-连通图.对G中任意一对顶点x和y,当d(x,y)=2时,d(x)+d(y)≥2[v/2]+3；当d(x,y)=3时,d(x)+d(y)≥2[v/2]-1；当d(x,y)=4时,d(x)+d(y)≥2[v/2]-5；当d(x,y)=5时,d(x)+d(y)≥2[v/2]-9,且在G的任意一个同构于K6的子图中都存在一个点”满足d(v)≥[v/2]+4,则G是λ5-最优的.(2)设G是阶至少为21的λ5-连通图.对G中任意一对顶点x和y,当d(x,y)=2时,d(x)+d(y)≥2[v/2]+5；当d(x,y)=3时,d(x)+d(y)≥2[v/2]+1；当d(x,y)=4时,d(x)+d(y)≥2[v/2]-3；当d(x,y)=5时,d(x)+d(y)≥2[v/2]-7,且在G的任意一个同构于K6的子图中都存在一个点v满足d(v)≥[v/2]+5,则G是超级-λ5的.第四章主要研究图的λk-最优性和超级性之间的关系.结果如下：设G是λ5-最优图.(1)若6(G)≥8,则对于i=1,2,3,4,G是λi-最优的,且对于i=1,2,3,G是超级-λi的；若6(G)>8,则G是超级-λ4的.(2)设G是无三角形图.若δ(G)≥6,则对于i=1,2,3,4,G是λi-最优的；若δ(G)>6,则对于i=1,2,3,4,G是超级-λi的.
