摘要
设G是有限简单无向图,使G-S的每个分支都包含至少k个点的边割S称为G的k-限制边割。G的k-限制边连通度λk(G)是G的k-限制边割之中最少的边数。定义ξk(G)=min{[U,U-]:U V(G),|U|=k,G[U]是连通的},若λk(G)=ξk(G),则称G是λk-最优的。若任意最小k-限制边割都孤立一个k阶分支,则称图G是超级-λk的。应用范型条件给出了图是λ3-最优和超级-λ3的充分条件。
For a finite,simple and undirected graph G,an edge-cut S is called a k-restricted edge-cut of G if every component of G-S has at least k vertices.The k-restricted edge connectivity λk(G) of G is the minimum cardinality of all k-restricted edge-cuts.Defining ξk(G)=min{|:UV(G),|U|=k and G[U] is connected},G is λk-optimal if λk(G)=ξk(G),and super-λk if every minimum restricted edge-cut isolates a component of k vertices.This paper shows Fan-type sufficient conditions for graphs to be λ3-optimal and super-λ3.
出处
《科学技术与工程》
2010年第6期1327-1332,共6页
Science Technology and Engineering
基金
国家自然科学基金项目(10901097)资助
关键词
3-限制边连通度
最优-3-限制边连通
超级-3-限制边连通
范型条件
3-restricted edge connectivity optimally 3-restricted edge connected super-3-restricted edge connected Fan-type condition