On super edge-connectivity of product graphs

摘要

For a connected graph G, the super edge-connectivity λ′(G) is the minimum cardinality of an edge-cut F in G such that G-F contains no isolated vertices. It is a more refined index than the edge-connectivity for the fault-tolerance of the network modeled by G. This paper deals with the super edge-connectivity of product graphs G1∗G2, which is one important model in the design of large reliable networks. Let Gi be a connected graph with order νi and edge-connectivity λi for i=1,2. We show that λ′(G1∗G2)⩾min{ν1λ2,ν2λ1,λ1+2λ2,2λ1+λ2} for ν1,ν2⩾2 and deduce the super edge-connectedness of G1∗G2 when G1 and G2 are maximally edge-connected with δ(G1)⩾2,δ(G2)⩾2. Furthermore we state sufficient conditions for G1∗G2 to be λ′-optimal, that is, λ′(G1∗G2)=ξ(G1∗G2). As a consequence, we obtain the λ′-optimality of some important interconnection networks.