λ′-最优无三角图的最小边度充分条件

刘爱霞，原 军，吴红梅(太原科技大学应用科学学院，太原 030024)

多处理机网络和通信网络能很容易的用一个图来模拟，其中顶点集对应处理机或交换机，边集对应通信线路。在网络设计中一个最基本的问题就是网络的可靠性。网络的可靠性可以通过图的连通度来度量，该网络的拓扑结构所对应的图的边连通度越大，网络越可靠。然而，具有相同边连通度的图可靠性却不一定相同。为了更精确的度量图的可靠性，Esfahanian和Hakimi[1]提出了限制边连通度的概念。最近的研究结果表明限制边连通度越大，网络越可靠，该结论已被王应前和李乔在文献[2]中证明。研究图的限制边连通度有助于对现在流行的互连网络的可靠性进行科学的评价，有很多关于图的限制边连通度的研究，见文献[3]-文献[8]。

当一个图中不含有三角形的时侯，这个图就被称作是无三角图。无三角图在互连网络设计方面有非常广泛的应用。因此，为了更好地度量互连网络可靠性，对无三角图的限制边连通度进行研究就显得非常必要。本文研究并证明了λ′-最优无三角图的最小边度的充分条件。而且，举例说明本文结果是最好的。

1 预备知识

本文所讨论的图均为无向图，先给出相关的术语和记号，文中未定义的术语和记号参见文献[9]。

2 主要结果及其证明

张昭在2007年给出了一个λ′-最优无三角图的最小边度充分条件：

定理1设G是n阶连通的无三角图，最小度δ(G)≥2.若ξ(G)≥n-1，则G是λ′-最优的。

本文给出比这个定理更好的一个充分条件。首先需要文献[1]中的一个定理。

引理1对每一个n≥4阶的连通图G，除星图K1,n-1外，都是λ′-连通的，且满足:

λ(G)≤λ′(G)≤ξ(G)

在给出本文主要结论之前，先证明一个重要引理。

ξ(G)≤|[{x,y},V(G){x,y}]|=|S(x)|+

|S(y)|+|[{x,y},U{x,y}]|≤|S(x)|+

|S(y)|+|U{x,y}|≤|S(x)|+|S(y)|+

(因为G是无三角图)

这与λ′(G)<ξ(G)的假设矛盾。定理证毕。

下面给出本文的主要结论及证明。

定理2设G是一个n阶的连通无三角图，最小度δ(G)≥2.若最小边度满足:

则G是λ′-最优的。

因此，U*是G的一个独立集。设u是U*中的一个点，则由U*的定义知|S(u)|=0.令v是NG[U](u)中的点，并且|S(v)|=min{|S(w)|∶w∈NG[U](u)}(因为<δ(G)≥2，所以v点是存在的)。令:

A1={w∈U{v}∶w与u相邻}，

A2={w∈U{u}∶w与v相邻}.

由于G是无三角图，且边uv∈E(G)，推出A1∩A2=φ.记ai=|Ai|，i=1,2,则：

ξ(G)≤d(u)+d(v)-2=|S(v)|+a1+a2

(1)

因为|S(v)|=min{|S(w)|∶w∈NG[U](u)}，即对任意的点x∈A1，均满足|S(x)|≥|S(v)|，所以有:

(2)

将式(1)、式(2)与假设|S|<ξ(G)结合，得|S(v)|+a1+a2≥ξ(G)>|S|>a1|S(v)|+|S(v)|，即:

a1|S(v)|

注意到δ(G)≥2，|S(u)|=0且d(u)=|S(u)|+a1+1=a1+1.由此推出a1≥1.因此:

(3)

显然，|U|≥a1+a2+2，即|U|-2≥a1+a2，

将其与式(1)结合，可得ξ(G)≤|S(v)|+a1+a2≤|S(v)|+|U|-2，再与式(3)结合可得到:

因此:

由定理2可以得出以下推论：

由定理2知，G是λ′-最优的。证明完毕。

参考文献：

[1] ESFAHANIAN A H，HAKIMI S L.On computing a conditional edge-connectivity of a graph[J].Information Proceeding Letters，1988，27(4)：165-199.

[2] 王应前，李乔.直径为2的图的超级边连通性质[J].上海交通大学学报，1999，33 (6)：646-649.

[3] BALBUENA C，CARMONA A，FBREGA J，FOIL M A.Superconnectivity of bipartite digraphs and Graphs[J].Discrete Mathematics，1999，197-198：61-75.

[4] BALBUENA C，GARCA-VZQEZ P，MARCOTE X.Sufficient conditions forλ′-optimality in graphs with girth[J].Journal of Graph Theory，2006，52：73-86.

[5] HELLWIG A，VOLKMANN L.Sufficient conditions for graphs to beλ′-optimal，super-edge-connected，and maximally edge-connected[J].Journal of Graph Theory，2005，48：228-246.

[6] LI Q L，LI Q.Super edge connectivity properties of connected edge symmetric graphs[J].Networks，1999，33：147-159.

[7] MENG J X.Optimally super-edge-connected transitive graphs[J].Discrete Mathematics，2003，260：39-248.

[8] 吴红梅，原军.超级λ3-最优二部图的充分条件[J].太原科技大学学报，2011，32(40)：332-336.

[9] BONDY J A，MURTY U S R.Graph Theory with Applications[M].New York：The Macmillan Press Ltd，1976.

[10] ZHANG Z.Sufficient conditions for restricted-edge-connectivity to be optimal[J].Discrete Mathematics，2007，307：2891-2899.