超限制边连通笛卡尔乘积图的边容错性

Edge fault-tolerance of super restricted edge-connected Cartesian product graphs

摘要: 如果G-F不连通且每个连通分支至少含有两个顶点，则连通图G的边子集F称为限制边割.如果图G的每个最小限制边割都孤立G中的一条边,则称G是超限制边连通的(简称超λ′).对于满足|F|≤m的任意子集FE(G),超λ′图G的边容错性ρ′(G)是使得G-F仍是超λ′的最大整数m.这里给出了

Abstract: A subset F of edges in a connected graph G is a restricted edge-cut if G-F is disconnected and every component has at least two vertices. A graph G is super restricted edge-connected (super-λ′ for short) if every minimum restricted edge-cut of G isolates at least one edge. The edge fault-tolerance ρ′(G) of a super-λ′ graph G is the maximum integer m for which G-F is still super-λ′ for any subset FE(G) with |F|≤m. It was shown that