秦学姣

(新疆医科大学 厚博学院，新疆 克拉玛依 834000)

在设计一个互连网络时，容错性是一个基本原则，边连通性是衡量互连网络容错性的一个重要指标。图G的边连通度，记作λ(G)，定义为使G不连通时需删除的最小边数。然而，边连通度往往低估了多处理系统的容错能力。在很多情况下，当故障边数大于边连通度时，一个具有故障边的网络仍可能是连通的，或者存在较大的连通分支[1-3]。因此，互连网络的容错性与带有故障边的网络的较大连通分支的顶点数密切相关。

假设F是图G的一故障边集，G-F是从G中删除F得到的图,u和v是图G-F中的两个顶点，我们关心的是G-F中u和v之间的边不相交无故障路径的数目。我们将此问题考虑为边故障条件下的Menger定理[4]。近年来，学者们对互连网络的Menger特性进行了大量的研究[5-7]。特别地，Qiao等[6]研究了条件故障下的超立方体和折叠超立方体的强Menger边连通性。

k-元n-立方体是一类重要的互连网络。一方面，其包括了传统的互连网络作为其子类，如环(1-元n-立方体)、超立方体(2-元n-立方体)和环面(k-元 2-立方体)。另一方面，目前已经建立了多个大型并行分布式计算系统，如Gray T3D、J-machine、iWarp和Blue Gene，都是基于k-元n-立方体的拓扑结构。近年来，k-元n-立方体的许多拓扑性质得到了广泛的研究[8-13]。例如，Li等[9]考虑了路限制条件下将路和圈嵌入到3-元n-立方体中的问题；Yuan等[11]研究了3-元n-立方体网络的g-好邻点条件可诊断性。目前，有关条件故障下k-元n-立方体的强Menger性的研究较少。本文研究了具有条件边故障的3-元n-立方体网络的较大连通分支和强Menger边连通性。……