2-Hamming图的强Menger边连通容错性

Edge Fault-Tolerance of Strongly Menger Edge Connected 2-Hamming Graphs

设G是连通图.若G的任一对顶点u,v之间有min{d(u),d(v)}条边不交的路,则称连通图G为强Menger边连通的.设G是强Menger边连通图,m是非负整数,若对任意满足|F|≤m的边子集F,G-F都是强Menger边连通图,则称G是m-边容错强Menger边连通图.证明了2-Hamming图H(n,k,2)是(4n-2)-边容错强Menger边连通的,其中n≥2,k≥5.

A connected graph G is strongly Menger edge connected if any two of its vertices u,v are connected by min{d(u),d(v)}edge-disjoint paths.Let G be a strongly Menger edge connected graph and m be a non-negative integer,G is said to be m-edge tolerant strongly Menger edge connected if G−F is strongly Menger edge connected for any edge subset F with|F|≤m.It is proved in this paper that the 2-Hamming graphs H(n,k,2)are(4n−2)-edge fault-tolerant strongly Menger edge connected for n≥2,k≥5.