论文部分内容阅读
设 S是连通图G中的一个边子集，若 G- S不连通且它的每个连通分支的阶至少为k,则称 S是 G的一个k限制边割.图 G的最小k限制边割的边数称为 G的 k限制边连通度，记为 Afc(G).当 k=2时，A2( G)也记作A(G).定义6(G)= min帆对:|X|= k, G[X]连通},其中 X= V(G)X.若 Afc(G)=(k(G),则称 G是极大k限制边连通的，简称Ak-最优的.如果图G的每个最小k限制边割都恰好孤立了一个k阶连通子图，那么称图G是超级k限制边连通的，简称超级-Ak的.2011年，Q in等人给出了一个图是A-最优的充分条件.本文第二章把这个结果推广到Ak(k=3,4)-最优的情况.2010年，王世英等人给出了图是超级-Y的充分条件.本文第三章把这个结果推广到超级-Ak的情况. 本文分为三章.第一章是预备知识，介绍了一些本文中将要用到的图论方面的基本概念和术语. 第二章给出了图G是λk(k=3,4)-最优的充分条件，主要结果如下： (1)设 G是一个围长g(G)≥5的 A3-连通图.若 G中不存在5个u1，u2,υi,υ2,υ3使得距离 d(ui,υj)≥3(i=1,2;j=1,2,3),则 G是λ3-最优的； (2)令 G是一个围长g(G)≥5的λ3-连通图.若 G中存在1个点 u使得对任意的x,y∈ V(G){u}有距离d(x,y)<2,则 G是λ3-最优的； (3)设 G是一个满足λ4(G)≤ζ4( G)的λ4-连通图且围长g(G)≥8.若 G中不存在6个点 Ui, U2, U3, Vi, V2, V3使得距离 d(Ui,Vj)>3(i,j=1,2,3),则 G是λ4-最优的. 第三章给出了连通图G是超级-Ak的充分条件，主要结果如下： 设 k是一个不小于3的正整数且G是一个阶至少为2k的图.如果对G中任意两个不相邻的顶点U, V满足|N(U)∩ N(v)|≥k+1且ζ《k(G)≤[V2]+ k,则排除一类特殊图外, G是超级-λk的.