二部图λ_3最优性的一个原子条件

An Atom Condition of λ_3-Optimality of Bipartite Graphs

设G=(V,E)是有限简单无向图,U是G的一个边割,k是一正整数.若G-U的每个分支的阶至少为k,则称U为G的一个k阶限制边割.定义G的k阶限制边连通度λk(G)为G的k阶限制边割中最少的边数,达到最小的称为λk割.定义ξk(G)=min{(F):F是G的k阶连通子图},其中(F)表示恰好有一个端点在F上的边的数目.如果λk(G)=ξk(G),则称G是λk最优图.本文给出了二部图λ3最优性的一个原子条件.

Let G be a finite, simple integer. U is a k-restricted edge cut k-restricted edge connectivity λk （G） and if the of G undirected graph, U an edge cut of G and k a pos order of every component of G - U is no less than k. is the cardinality of a minimum k-restricted edge cut, itive The aλkcut. Let （F） -F is a subgraph of G - is the edge number exactly with ζk （G） = min （F） ：F is a k-conneted subgraph of G G is a A k-optimal This paper presents an atom condition of λ3-optimality of bipartite graphs one end vertex in F and graph if λ k （G） = ζk （G）.