图的边连通度的一些结果

对不含完全子图Kr+1的图进行了研究,当图G满足λ<δ时,运用Turán定理,通过分析图的边连通度与图的度序列之间的关系,得出了图的边连通度的一些结果.     

图是超级-λ3的邻域条件

设G是有限简单无向图, k是正整数,使G-S的每个分支都包含至少k个点的边割S称为G的k-限制边割。若任意最小k-限制边割都孤立一个k阶连通子图,则称图G是超级-λk 的。本文应用邻域条件给出了图是超级-λ3 的充分条件。     

邻接树图的连通度

设Ｇ是任一连通图，Ｈ是Ｇ的邻接树图，κ（Ｈ），λ（Ｈ），δ（Ｈ）分别是Ｈ的连通度，边连通度和最小次，则κ（Ｋ）＝λ（Ｈ）＝δ（Ｈ）。     

k-正则图的可扩性质

设G是k正则（k-1）－边连通的简单图，F是G的一个边集且|F|≤k-1。本文证明了如下结论：如果G有完美匹配，则G－F也有完美匹配。于是，我们推出：如果G有完美匹配，则G是1－可扩图。     

围长为3的点可迁图的3限制边连通度

设G是阶至少为6的k正则连通图.如果G的围长等于3,那么它的3限制边连通度 λ3(G)≤3k-6.当G是3或者4正则连通点可迁图时等号成立,除非G是4正则图并且 λ3(G)=4.进一步,λ3(G)=4的充分必要条件是图G含有子图K4.     

完全对换网络的限制连通度

完全对换网络是基于 Cayley 图模型的一类重要互连网络. 一个图 G 的 k-限制点(边)连通度是使得 G-F 不连通且每个分支至少有 k 个顶点的最小点(边)子集 F 的基数, 记作 \kappa_{k}(\lambda_{k}). 它是衡量网络可靠性的重要参数之一, 也是图的容错性的一种精化了的度量. 一般地, 网络的 k-限制点(边)连通度越大, 它的连通性就越好. 证明了完全对换网络 CT_{n} 的 2-限制点(边)连通度和 3-限制点(边)连通度, 具体来说: 当 n\geq4 时, \kappa_{2}(CT_{n})=n(n-1)-2, \kappa_{3}(CT_{n})=\frac{3n(n-1)}{2}-6; 当 n\geq3 时, \lambda_{2}(CT_{n})=n(n-1)-2, \lambda_{3}(CT_{n})=\frac{3n(n-1)}{2}-4.     

正则图的环边连通性和环连通性之间的关系

研究了一般3 正则连通图G的环边连通性和环连通性之间的关系,证明了G的环边连通度等于其环连通度。讨论了G的环连通度与环点连通度之间的关系,指出当G的顶点个数不少于其环连通度的6倍时,其环连通度等于其环点连通度。     

图的λk最优性和超级性的充分条件

分别给出了直径为2的图的λ3最优性和不含三角的图是超级λk的一个充分条件,讨论了不含三角的图的λk最优性和λk超级性的关系,这些结果在网络可靠性分析中有一定应用．     

有向图边接通度的下界

有向图常模拟互联网络.因此,对于网络的客错性,有向图的边连通度是一个重要的度量.文章用度序列给出了有向图的边连通度的新的下界.     

图是超级-λ′的充分条件

设G=(V,E)是有限简单无向图.如果G的每个最小限制边割都孤立出一条边,则称G是超级-λ′的.笔者在一定意义上改进了文献[7]给出的图为超级-λ′的一个充分条件.