k阶限制边连通度最优的一个充分条件

摘要：

设S是图G的一个边子集,若G-S不连通且每个分支的阶至少为k,则称S为G的一个k-限制边割.若G有k-限制连割,G的最小k-限制边割的边数称为G的k阶限制边连通度,记为λk(G).记ξk(G)=min{|[X,]|∶|X|=k,G|X|连通},若λk(G)=ξk(G),则称G是λK-最优的.证明了若对G中任意一对不相邻的顶点x,y都有d(x)+d(y)≥n+2(k-2),且G不是G*k图,则G是λk-最优的.

关键词：图、k阶限制边连通度、λk-最优

所属期刊栏目：8

分类号：O157.5(代数、数论、组合理论)

在线出版日期：2008-08-26（万方平台首次上网日期，不代表论文的发表时间）

页数：共3页

页码：3579-3581