图是超限制性边连通的充分条件(英文)

Sufficient Conditions for Graphs to be Super Restricted Edge Connected

设G=(V,E)是连通图.边集S E是一个限制性边割,如果G-S是不连通的且G—S的每个分支至少有两个点.G的限制性连通度λ'(G)是G的一个最小限制性边割的基数.G是λ'-连通的,如果G存在限制性边割.G是λ'-最优的,如果λ'(G)=ζ(G),其中ζ(G)是min{d(x)+d(y)-2:xy是G的一条边}.进一步,如果每个最小的限制性边割都孤立一条边,则称G是超限制性边连通的或是超-λ'.G的逆度R(G)=∑_(v∈V) 1/d(v),其中d(v)是点v的度数.我们证明了G是λ'-连通的且不含三角形,如果R(G)≤2+1/ζ-ζ/((2δ-2)(2δ-3))+(n-2δ-ζ+2)/((n-2δ+1)(n-2δ+2)),则G是超-λ'.

Let G =（V,E） be a connected graph.An edge set S E is a restricted edge cut,if G - S is disconnected and every component of G - S has at least two vertices.The restrictededge connectivityλ＇（G） of G is the cardinality of a minimum restricted edge cut of G.A graphG isλ＇-connected,if restricted edge cuts exist.A graph G is calledλ＇-optimal,ifλ＇（G） =ξ（G）,whereξ（G） =min{ξ（e） = d（u） ＋d（v） -2：e = uv∈E}.Furthermore,if every minimumrestricted edge cut is a set of edges incident to a certain edge,then G is said to be super restrictededge connected or super-λ＇ for simplicity.Inverse degree of G is R（G）=Σ_（v∈V）1/（d（v））,where d（v）denotes the degree of the vertex v.We show that let G be aλ＇-connected triangle-free graph.IfR（G）≤2＋（1/δ）-（ξ/（（2δ-2）（2δ-3）））＋（（n-2δ-ξ＋2）/（n-2δ＋1）（n-2δ＋2））,then G is super-λ＇.