On super edge-connectivity of product graphs

For a connected graph G, the super edge-connectivity lambda'(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 G(1)*G(2), which is one important model in the design of large reliable networks. Let G(i) be a connected graph with order nu(i) and edge-connectivity lambda(i) for i = 1, 2. We show that lambda '(G(1)G(2)) >= min{nu(1)lambda(2), nu(2)lambda(1),lambda(1) + 2 lambda(2),2 lambda(1) + lambda(2)} for nu(1), nu(2) >= 2 and deduce the super edge-connectedness of G(1)*G(2) when G(1) and G(2) are maximally edge-connected with delta(G(1)) >= 2, delta(G(2)) >= 2. Furthermore we state sufficient conditions for G(1)*G(2) to be lambda'-optimal, that is, lambda'(G(1)*G(2)) = xi(G(1)*G(2)). As a consequence, we obtain the lambda'-optimality of some important interconnection networks. Crown Copyright (C) 2008 Published by Elsevier Inc. All rights reserved.