λ′-最优图的充分条件

Sufficient conditions for graphs to be λ′-optimal

设G=(V,E)是一个连通图.边集SE,如果G-S不连通且G-S的每个连通分支至少有2个点,则称S是一个限制性边割.限制性边连通度λ′(G)就是G的最小限制性边割的基数.如果限制性边割存在,则称G是λ′-连通的.如果λ′(G)=ξ(G),则G是λ′-最优或者极大限制性边连通的,其中ξ(G)=min{|[X,Y]|:XV,|X|=2,G[X]连通}.图G的逆度是指R(G)=∑_v∈V 1/d(v).在此基础上,主要得到了:如果G是λ′-连通围长大于等于5的n阶图,且δ(G)≥2,如果R(G)小于某个关于最小度和顶点数的值,则G是λ′-最优的.对于不含钻石的图也得到了类似的结果.

Let G=(V,E) be a connected graph.An edge set S■E is a restricted edge cut,ifG -S is disconnected and every component of G -S contains at least two vertices.The restricted edge connectivity λ’(G) of G is the cardinality of a minimum restricted edge cut of G.A graph G is λ’-connected,if restricted edge cuts exist.A graph G is called λ’-optimal,if λ’=ξ(G),where ξ(G)=min{|[x,y]|:X■V,|X|=2,G[X] is connected}.The inverse degree of graphs is R(G)=∑v∈V1/(d(v)).In this paper,we obtain the main result below:let G be a λ’-connected graph,girth g≥5 and δ(G)≥2,if R(G) is smaller than some value about n and δ(G),then,G is λ’-optimal.We also obtain similar results for graphs which do not contain the diamond.