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

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

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

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

1 预备知识

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

2 主要结果及其证明

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

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

本文给出比这个定理更好的一个充分条件。……