轮图的边容错强Menger边连通性

Edge-Fault-Tolerant Strong Menger Edge Connectivity of Wheel Networks

摘要: 连通性是评估互连网络可靠度和容错性的一个非常重要的参数。若对于连通图G中的任意两个顶点x,y，它们之间有min{deg_G(x),deg_G(y)}条边不相交的路，则连通图G是强Menger边连通的。若对于任意的边集F_e⊆E(G)且▏F_e▏≤m，G-F_e仍保持强Menger边连通性，则图G是m-边容错强Menger边连通的。若对于任意的边集F_e⊆E(G)且▏F_e▏≤m和δ(G-F_e)≥2，G-F_e仍保持强Menger边连通性，则图G是m-条件边容错强Menger边连通的。在这篇文章中，我们证明CW_n(n≥4)是(2n-4)-边容错强Menger边连通的。此外，我们给出例子来说明我们保持强Menger边连通性的有关故障边的数量是最大值，即是最优的。

Abstract: Connectivity is an important measurement to evaluate the reliability and fault tolerance of inter-connection networks. A connected graph is called strongly Menger edge connected if for any two distinct vertices x, y in G, there are min{deg_G(x),deg_G(y)} edge-disjoint paths between x and y. A graph G is called m-edge-fault-tolerant strongly Menger edge connected if G-F_e remains strongly Menger edge connected for an arbitrary set F_e⊆E(G) with ▏F_e▏≤m . A graph G is called m-conditional edge-fault-tolerant strongly Menger edge connected if remains strongly Menger edge connected for an arbitrary set F_e⊆E(G) with ▏F_e▏≤m and δ(G-F_e)≥2 . In this paper, we show that CW_n is (2n-4)-edge-fault-tolerant strongly Menger edge connected δ(G-F_e)≥2 for (n≥4) and (6n-14)-conditional edge-fault-tolerant strongly Menger edge con-nected for n≥5 . Moreover, we present some examples to show that our results are all optimal with respect to the maximum number of tolerated edge faults.