论文部分内容阅读
令G=(V,E)是一个连通图.定义[A,B]为一端点在A中,另一端点在B中的边的集合.G的边割是指形为[U,(U)]的E(G)的子集,其中U是V(G)的非空子集,(U)=V(G)-U.设S(∈)E是G的一个边割,如果G-S的每个连通分支至少有k个顶点,那么称S是G的一个k-限制边割.若G存在k-限制边割,则称G为λk-连通图.称G的所有k-限制边割中所含边数最少的边割为G的λk-割,λk-割所含的边数称为G的k-限制边连通度,记为λk(G).令ξk(G)=min{|[X,(X)]|:|X|=k,G[X]是连通的}.若λk(G)=ξk(G),则称G是λk-最优的.2004年,Volkmann等提出了在邻域交条件下,图是λ-最优的.本文把这些结果推广到λk(G)-最优的情况.文章主要讨论了图在邻域交条件下的高阶限制边连通的最优性问题. 本文分为四章.第一章是预备知识,介绍了一些本文中将要用到的图论方面的基本概念和术语. 第二章简要介绍了限制边连通度的发展现状. 第三章给出了图G是λk-连通的邻域交条件.进一步,在某些条件下G是λk-最优的.主要结果如下: (1)设k是一个正整数且G是一个阶不小于2k的图.若对于G中任意不相邻的顶点u,v都满足|N(u)∩ N(v)|≥k,则G是λk-连通的且λk(G)≤ξk(G). (2)设k是一个不小于3的正整数且G是一个阶不小于2k的图.若对于G中任意不相邻的顶点u,v都满足|N(u)∩N(v)|≥k且ξk(G)≤(「)v/2」+k,则排除一类特殊图外(见第三章),G是λk-最优的. (3)设k是一个不小于4的正整数且G是一个阶不小于2k的图.若对于G中任意不相邻的顶点u,v都满足|N(u)∩N(v)|≥k且ξk(G)≤(「)v/2」+k,则G是λk-最优的. 第四章给出了连通图G是λk-最优的充分性条件.主要结果如下: (1)设k是一个不小于2的正整数且G是一个阶不小于2k的λk-连通图.设S=[X,Y]是G的一个满足|X|≥k+1与|Y|≥k+1的λk-割.如果对于G中任意不相邻的顶点u,v,当u,v都不在三角形中时满足|N(u)∩N(v)|≥k+1;当u和v中至少有一个在三角形中时满足|N(u)∩N(v)|≥2k-1,那么G[X]和G[Y]中分别存在一条k-路. (2)设k是一个不小于2的正整数且G是一个阶不小于2k的图.如果对于G中任意不相邻的顶点u,v,当u,v都不在三角形中时满足|N(u)∩N(v)|≥k+1;当u,v至少有一个在三角形中时满足|N(u)∩N(v)|≥2k-1,那么G是λk-最优的.