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

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

作　　者：南俐贞 王世英 

机构地区：[1]山西师范大学数学与计算机科学学院,山西 太原

出　　处：《应用数学进展》2023年第6期3069-3085,共17页Advances in Applied Mathematics

摘　　要：连通性是评估互连网络可靠度和容错性的一个非常重要的参数。若对于连通图G中的任意两个顶点x,y,它们之间有min{degG(x),degG(y)}条边不相交的路,则连通图G是强Menger边连通的。若对于任意的边集Fe⊆E(G)且▏Fe▏≤m,G-Fe仍保持强Menger边连通性,则图G是m-边容错强Menger边连通的。若对于任意的边集Fe⊆E(G)且▏Fe▏≤m和δ(G-Fe)≥2,G-Fe仍保持强Menger边连通性,则图G是m-条件边容错强Menger边连通的。在这篇文章中,我们证明CWn(n≥4)是(2n-4)-边容错强Menger边连通的。此外,我们给出例子来说明我们保持强Menger边连通性的有关故障边的数量是最大值,即是最优的。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{degG(x),degG(y)} edge-disjoint paths between x and y. A graph G is called m-edge-fault-tolerant strongly Menger edge connected if G-Fe remains strongly Menger edge connected for an arbitrary set Fe⊆E(G) with ▏Fe▏≤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 Fe⊆E(G) with ▏Fe▏≤m and δ(G-Fe)≥2 . In this paper, we show that CWn is (2n-4)-edge-fault-tolerant strongly Menger edge connected δ(G-Fe)≥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.

关 键 词：互连网络 容错性 轮图 强Menger边连通性 

分 类 号：O17[理学—数学]