论文部分内容阅读
图的限制连通性问题一直是图论的一个核心课题.由于限制连通度能度量网络的可靠性和容错性,伴随着互连网络的快速发展,近年来对图的限制连通性进行了广泛研究.设G=(V, E)是有限简单无向图,其中V=V(G)和E=E(G)分别是G的顶点集和边集.设S是连通图G的一个边割,若G-S的每个连通分支都至少有k个点,则称S是G的一个k-限制边割.称G中所含边数最少的k-限制边割为λk-割.记G的k-限制边连通度λk=λk(G)为λk-割所含的边数.定义ξk(G)=min{|[X,(X)]|:X(C)V(G),|X|=k,G[X]是连通子图},若λk(G)=ξk(G),则称G是λk-最优图. 在本文中,我们主要研究几类图限制边连通度的一些问题.本文共分三章: 第一章,介绍了文章所涉及的一些概念、术语和符号. 第二章,给出了λ5-最优图的一个充分条件.主要结果如下: 设G是一个v≥17,δ≥([)v/2」-4且λ5(G)≤ξ5(G)的λ5-连通图,若 (i)G中每个导出六圈以及任意由一条边相连的两个三角形的粘合图中都存在非粘合点u满足d(u)≥([)v/2」-2; (ii)G中每个导出五圈以及任意两个三角形的粘合图中都存在非粘合点v满足d(v)≥([)v/2]; (iii)G中每个四圈上都存在一点w满足d(w)≥([)v/2」+4,则G是λ5-最优图. 第三章,给出了λ4-最优图的一个度条件.主要结果如下: 设G是一个v≥11的λ4-连通图,若 (i)对于任意x,y∈V(G),当d(x,y)=4时,max{d(x),d(y)}≥([)v/2」-3; (ii)对于任意x,y∈V(G),当d(x,y)=3时,max{d(x),d(y)}≥([)v/2」-1; (iii)对于任意x,y∈V(G),当d(x,y)=2时,max{d(x),d(y)}≥([)v/2」+1;则G是λ4-最优图.