在本文中,只研究无向简单连通图,对文中未出现的术语和定义

参考文献[1].设G=(V,E)是连通图,d_G(v)表示G中点v的度(简写为d(v)),δ(G)是G的最小度.进而,设SV,G[S]是由S导出的子图,G-S是点集V-S导出的G的子图并且令图G的围长g(G)是G中最短圈的长度.令X,YV,[X,Y]表示G的一条边的端点在X中、另一个端点在Y中的边的集合.

一个处理器网络或通信网络可以用图G=(V,E)表示,其中V中的每个点表示处理器或交换机,E中的每条边表示连接处理器或交换机的线路.网络设计的一个基本要求是网络的可靠性.连通图G的边割S是一些边的集合,G去掉S后不连通.G的边连通度λ(G)就是G的最小边割的基数.边连通度λ(G)是衡量网络可靠性和容错性的一个重要参数.我们知道λ(G)≤δ(G),一般地,λ(G)越大网络越稳定,但是,在λ(G)的定义中没有对G-S的分支进行限制.因此,有研究者给出了限制性边连通度的定义^[2],具体如下:

边集SE,如果G-S不连通且G-S 的每个连通分支至少两个点,则S是G的限制性边割.G的最小限制性边割的基数就是G的限制性边连通度,用λ'(G)表示.如果S是一个限制性边割且|S|=λ'(G),则称S是一个λ'-割.Esfahanian等^[2]证明了如下结果:

定理1^[2] 对任意的至少有4个点的连通图G,且不同构于星图K_1,n-1,则λ'(G)存在且有λ'(G)≤ξ(G),其中ξ(G)=min{ξ(e)=d(u)+d(v)-2:e=uv∈E}是G的最小边度.

如果λ'(G)=ξ(G),则称G是λ'-最优的.如果G有λ'-割,则称G是λ'-连通的.因此限制性边连通度是经典边连通度的推广,可以更加精确地衡量大规模并行处理系统的可靠性和容错性,从而,受到了很多学者的关注.

设图G没有孤立点,定义G的逆度R(G)=∑_v∈V1/(d(v)).逆度最早是由计算机的Graffiti 猜想引起人们注意的^[3],此后其他学者也研究了逆度的其他性质^[4-7].本文中给出了关于R(G),δ(G),ξ(G)和n的函数的图是λ'-最优的充分条件.

首先,研究图的λ'-最优性并有如下结果.

定理2 设G是λ'-连通围长大于等于5的图,δ(G)≥2.若n≤2δ+1,则G是λ'-最优的.

证明 反证法.设λ'<ξ,则存在一个λ'-割S=[X,Y],有|X|,|Y|≥2.令X₁X,且X₁中的每个点至少关联[X,Y]中的一条边,X₀=X-X₁.注意到围长大于等于5,分两种情况讨论.

情形1 X₀=.

根据假设X中的每个点至少关联[X,Y]中的一条边,取边e=xy∈E(G[X]),有

ξ(G)≤d(x)+d(y)-2=|N(x)|+|N(y)|-

2=|(N(x)∩X)\{y}|+|N(x)∩Y|+

|(N(y)∩X)\{x}|+|N(y)∩Y|≤

|[{x,y},Y]|+|[X\{x,y},Y]|=

|[X,Y]|=λ'(G),

矛盾.

情形2 X₀≠.

情形2.1 G[X₀]是独立集.令x∈X₀,y∈X₁且xy∈E(G[X]),则N(x)X₁.类似于情形1,一样可以得到矛盾.

情形2.2 设边e=xy∈E(G[X₀]).由于N(x)X,N(y)X,有

|X|=|X₁|+|X₀|≥|N(x)∪N(y)-x-y|+

2≥min{d(x)-1,d(y)-1}+2≥δ+1.

同样地,有|Y|≥δ+1,则n≥2δ+2,矛盾.

下面介绍一个有用的引理.

引理1 设G是λ'-连通围长大于等于5的图,且δ(G)≥2,则存在一个λ'-割[X,Y],其中两个不交点集X,YV(G),X∪Y=V(G)且|[X,Y]|=λ'.如果λ'<ξ,则|X|,|Y|≥ξ+2.

证明反证法 根据假设有|X|,|Y|≥2.令X₁X,且X₁中的每个点至少关联[X,Y]中的一条边,X₀=X-X₁.注意到围长大于等于5,分两种情况讨论.

情形1 X₀=.

则X中的每个点至少关联[X,Y]中的一条边.取边e=xy∈E(G[X]),可以得到

ξ(G)≤d(x)+d(y)-2=|N(x)|+|N(y)|-

2=|(N(x)∩X)\{y}|+|N(x)∩Y|+

|(N(y)∩X)\{x}|+|N(y)∩Y|≤|[{x,

y},Y]|+|[X\{x,y},Y]|=|[X,Y]|=λ'(G).

矛盾.

情形2 X₀≠.

情形2.1 G[X₀]是独立集.设x∈X₀,y∈X₁且xy∈E(G[X]),则N(x)X₁.注意到围长大于等于5,有

ξ(G)≤d(x)+d(y)-2=|N(x)|+|N(y)|-

2=|(N(x)∩X)\{y}|+|(N(y)∩X)\{x}|+

|N(y)∩Y|=|(N(x)∩X)\{y}|+

|(N(y)∩X₀)\{x}|+|N(y)∩X₁|+|N(y)∩

Y|≤|(N(x)∩X)\{y}|+

∑_{u∈(N(y)∩X0)\{x}}|N(u)∩X₁|+|N(y)∩X₁|+

|N(y)∩Y|≤|[{x,y},Y]|+

|[X\{x,y},Y]|=|[X,Y]|=λ'(G).

矛盾.

情形2.2 取一条边e=xy∈E(G[X₀]).因为围长大于等于5以及N(x)∩N(y)=,N(x)X,N(y)X.因此,

|X|=|X₁|+|X₀|≥d(x)-1+d(y)-1+2≥d(x)+d(y)≥ξ(e)+2≥ξ(G)+2.

同样地,有|Y|≥ξ(G)+2.

推论1 设G是λ'-连通围长大于等于5的n阶图,且δ(G)≥2.若n≤2ξ(G)+3,则G是λ'-最优的.

引理2^[5]

(i)设a₁,a₂,…,a_p,A是正实数且∑^p_i=1a_i≤A,则

∑^p_i=1(1/a_i)≥p²/A.

(ii)如果a₁,a₂,…,a_p,A是正整数且∑^p_i=1a_i≤A,a,b是整数有A=ap+b且0≤b≤p,则

∑^p_i=1(1/a_i)≥(p-b)/a+b/(a+1).

其中等号成立的充要条件是p-b个a_i等于a,其余的a_i等于a+1.

(iii)设f(x)是区间[L,R]上的连续凸函数,若l,r∈[L,R],且l+r=L+R,则f(L)+f(R)≥f(l)+f(r).

定理3 设G是λ'-连通围长大于等于5的n阶图,且δ(G)≥2,如果

R(G)<2+(n-2δ-ξ+1)/((n-2δ+1)(n-2δ))+1/δ-(ξ-1)/(2δ(2δ-1)),

则G是λ'-最优的.

证明 设G不是λ'-最优的,即λ'<ξ.根据引理1,则存在一个λ'-割[X,Y],其中两个不交点集X,YV(G),X∪Y=V(G)且|[X,Y]|=λ',使得

|X|,|Y|≥ξ(G)+2≥2δ,

有2δ≤|X|,|Y|≤n-2δ.

进一步地,∑_x∈Xd(x)≤|X|(|X|-1)+λ'.由引理2的(ii),有

∑_x∈X1/(d(x))≥(|X|-λ')/(|X|-1)+(λ')/(|X|)=1+1/(|X|-1)-(λ')/(|X|(|X|-1)).

图G有一个度为δ的点v.不失一般性地,假设v∈Y,则∑_y∈Y,vd(y)≤(|Y|-1)²+λ'.由引理2的(ii),有

∑_y∈Y1/(d(y))≥1/δ+(|Y|-1-λ')/(|Y|-1)+(λ')/(|Y|)=1+1/δ-

(λ')/(|Y|(|Y|-1)).

由1/(|X|-1)≥1/(n-2δ-1),可以得到

R(G)≥2+1/δ+1/(n-2δ-1)-(λ')/(|Y|(|Y|-1))-(λ')/(|X|(|X|-1)).

考虑函数f(t)=1/(t(t-1)),容易验证t>0时,f ″(t)>0,因此f是凸的.又由于|X|,|Y|≥2δ,|X|+|Y|=n.将引理2的(iii)应用到函数f(t),则有

1/(|X|(|X|-1))+1/(|Y|(|Y|-1))≤

1/(2δ(2δ-1))+1/((n-2δ)(n-2δ-1)).

又因为λ'≤ξ-1,有

R(G)≥2+1/δ+1/(n-2δ-1)-

(ξ-1)/(2δ(2δ-1))-(ξ-1)/((n-2δ)(n-2δ-1))=2+

(n-2δ-ξ+1)/((n-2δ+1)(n-2δ))+1/δ-(ξ-1)/(2δ(2δ-1)).

矛盾.

钻石图就是完全图K₄去掉任意一条边.类似于引理1有如下结论:

引理3 设G是λ'-连通最小度大于等于2且不含钻石的图,S=[X,Y]是一个λ'-割.不妨设|X|≤|Y|,存在一个点v∈X,且v在一个三角形上,有|N(v)∩Y|≥2.如果λ'<ξ,则|X|,|Y|≥ξ+1.

证明类似于引理1.

推论2 设G是λ'-连通最小度大于等于2且不含钻石的图,S=[X,Y]是一个λ'-割.不妨设,|X|≤|Y|,存在一个点v∈X,且v在一个三角形上,有|N(v)∩Y|≥2.如果n≤2ξ(G)+1,则G是λ'-最优的.

定理4 设G是λ'-连通最小度大于等于2且不含钻石的图,S=[X,Y]是一个λ'-割.不妨设|X|≤|Y|,存在一个点v∈X,且v在一个三角形上,有|N(v)∩Y|≥2.如果

R(G)<2+(n-2δ-ξ+2)/((n-2δ+1)(n-2δ))+1/δ-

(ξ-1)/((2δ-2)(2δ-1)),

则G是λ'-最优的.

证明 设G不是λ'-最优的,根据引理3,有|X|,|Y|≥ξ+1≥2δ-1.进而有

∑_y∈Yd(y)≤|Y|(|Y|-1)+λ'.

由引理2的(ii),有

∑_y∈Y1/(d(y))≥(|Y|-λ')/(|Y|-1)+(λ')/(|Y|)=1+1/(|Y|-1)-

(λ')/(|Y|(|Y|-1)).

图G有一个度为δ的点v.不妨设v∈X.那么有

∑_x∈X,vd(x)≤(|X|-1)²+λ',

由引理2的(ii),得

∑_x∈X1/(d(x))≥1/δ+(|X|-1-λ')/(|X|-1)+(λ')/(|X|)=

1+1/δ-(λ')/(|X|(|X|-1)).

又因为1/(|Y|-1)≥1/(n-2δ),则有

R(G)≥2+1/δ+1/(n-2δ)-(λ')/(|Y|(|Y|-1))-(λ')/(|X|(|X|-1)).

考虑函数g(t)=1/(t(t-1)),容易验证t>0时,g″(t)>0,所以g是凸函数.因为 |X|,|Y|≥2δ-1,|X|+|Y|=n,应用引理2的(iii),有

1/(|X|(|X|-1))+1/(|Y|(|Y|-1))≤

1/((2δ-2)(2δ-1))+1/((n-2δ+1)(n-2δ)).

注意到λ'≤ξ-1,则

R(G)≥2+1/δ+1/(n-2δ)-(ξ-1)/((2δ-2)(2δ-1))-(ξ-1)/((n-2δ+1)(n-2δ))=2+

(n-2δ-ξ+2)/((n-2δ+1)(n-2δ))+1/δ-

(ξ-1)/((2δ-2)(2δ-1)).

矛盾.