论文部分内容阅读
设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是λ5-最优的. (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的子图中都存在一个点v满足d(v)≥(「)v/12」+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)若δ(G)≥8，则对于i=1，2，3，4，G是λi-最优的，且对于i=1，2，3，G是超级-λi的;若δ(G)＞8，则G是超级-λ4的. (2)设G是无三角形图.若δ(G)≥6，则对于i=1，2，3，4，G是λi-最优的;若δ(G)＞6，则对于i=1，2，3，4，G是超级-λi的.