不含三角形的图的λ3-最优性的充分条件

设G=(V,E)是一个连通图,边集S(?)E是一个3-限制性边割,如果G-S是不连通的并且G-S的每个分支至少有三个点.图G的3-限制性边连通度λ_3(G)是G中最小的一个3-限制性边割的基数.图G是λ_3(G)连通的,如果3-限制性边割存在.G是λ_3-最优的,如果λ_3(G)=ξ_3(G),其中ξ_3(G)=min{|U,(?)]|:U(?)V,|U|=3 and GU]是连通的).GU]表示V的子集U的导出子图,(?)=V\U表示U的补.U,(?)]是一条边的一个端点在U中另一个端点在(?)中的边的集合.本文给出了不含三角形的图是λ_3-最优的一些充分条件.

Sufficient Conditions for λ3-Optimality of Triangle-Free Graphs

Let G=(V,E)be a connected graph.An edge set S C E iS a 3-restrictededge-cut,if G-S is disconnected and every component of G-S has at least three vertices.The 3-restricted-edge-connectivity λ3 (G)of G is the cardinality of a minimum 3-restricted-edge-cut of G.A graph G is λ3-connected,if 3-restricted-edge-cuts exist.A graph G is called λ3-optimal,if λ3(G)=ξ3(G),whereξ 3(G)=min{|U,￣U]|:∪ C V,|U| =3 and GU]is connected}.GU] is the subgraph of G induced by the vertex subset U C＿ V,and U=V＼U is the complement of U.U,￣U] is the set of edges with one end in U and the other in U.In this paper,we give some sufficient conditions for triangle-free graphs to be λ3-optimal.