论文部分内容阅读
设S是图G的一个边子集，若G-S不连通且每个分支的阶至少为k，则称S为G的一个k-限制边割。若G有k-限制连割，G的最小k-限制边割的边数称为G的k阶限制边连通度，记为λk（G）．记ξk（G）=min{｜[X，^-X]｜：｜X｜=k，G｜X｜连通}，若λk（G）=ξk（G），则称G是λk-最优的。证明了若对G中任意一对不相邻的顶点x，Y都有d（x）＋d（y）≥n＋2（k-2），且G不是Gk^＊图，则G是λk-最优的。