关于图的K阶限制边连能度一些问题的研究

关于图的K 阶限制边连能度一些问题的研究图的限制连通性问题一直是图论的一个核心课题 . 由于限制连通度能度量网络的可靠性和容错性 , 伴随着互连网络的快速发展, 近年来对图的限制连通性进行了广泛研究.设G=(V E)是有限简单无向图，其中V=V(G刖E=E(G汾加J是G的 顶点集和边集. 设 S 是连通图 G 的一个边割 , 若 G-S 的每个连通分支都至少有k个点,则称S是G的一个k-限制边割.称G中所含边数最少的k-限制边割为入k- 割.记G的k-限制边连通度入k=入k(G)为入k-割所含的边数.定义工k(G尸min|X,X|:X V(G),|X|=k,GC是连通子图，若入 k(G)=工 k(G),则称 G是入k-最优图.在本文中，我们主要研究几类图限制边连通度的一些问题.本文共 分三章：第一章，介绍了文章所涉及的一些概念、术语和符号.第二章，给出了入 5-最优图的一个充分条件.主要结果如下：设G是一个v>17,6v-4 且入5(G) <己5(G)的入5-连通图，若(i)G中每个导出六圈以及任意由一条边相连的两个 三角形的粘合图中都存在非粘合点u满足d(u)v-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 时,maxd(x),d(y)刁v/2-3 ; (ii)对于任意 x,y C V(G),当 d(x,y)=3 时,maxd(x),d(y)> v/2-1 ； (iii) 对于任意x,y V(G),当 d(x,y)=2 时,maxd(x),d(y) > v/2+1 ；则 G是入 4-最优图.