二部图是极大5限制边连通的充分条件

RA Girth Condition for Maximally 5-Restricted Edge-Connected Bipartite Graphs

设G=(V,E)是一个连通图.称一个边集合S■E是一个k限制边割,如果G-S的每个连通分支的阶至少为k.记G中所有k限制边割的边数的下界为λ_k(G).定义ξ_k(G)=min{X,■∶X=k,G[X]连通},其中■=V(G)\X.如果λk(G)=ξk(G),称图G是极大k限制边连通的.本文给出了包含极大(4,4)-距离点集对的连通二部图是极大5限制边连通的围长条件.

For a connected network G,an edge set S is a k-restricted edge cut if G-S is disconnected and every component of G-S has at least k vertices. The restricted edge connectivity of G,denoted by λ5(G),is defined as the minimum cardinality of all k-restricted edge cuts. Let ξ5(G)=min{X,X∶■ = k,G[X]is connected,},where ■ =V(G)\X. A graph is maximally k-restricted edge connected if λk(G)= ξk(G). In this paper,a girth condition for maximally 5-restricted edge is the connected bipartite graphs with maximally(4,4)-distance set pair of vertices.