Bounded edge-connectivity and edge-persistence of Cartesian product of graphs

摘要

The bounded edge-connectivity lambda(k)(G) of a connected graph G with respect to k(>= d(G)) is the minimum number of edges in G whose deletion from G results in a subgraph with diameter larger than k and the edge-persistence D+(G) is defined as lambda(d(g))(G), where d(G) is the diameter of G. This paper considers the Cartesian product G(1) x G(2), shows lambda(k1+k2) (G(1) x G(2)) >= lambda(k1), (G(1)) + lambda(k2) (G(2)) for k(1) >= 2 and k(2) >= 2, and determines the exact values of D+ (G) for G = C-n x P-m, C-n x C-m, Q(n) x P-m and Q(n) x C-m.