The k-restricted edge-connectivity of a product of graphs

This work deals with a generalization of the Cartesian product of graphs, the product graph G"m*G"p introduced by Bermond et al. [J.C. Bermond, C. Delorme, G. Farhi, Large graphs with given degree and diameter II, J. Combin. Theory, Series B 36 (1984), 32-48]. The connectivity of these product graphs is approached by studying the k-restricted edge-connectivity, which is defined as the minimum number of edges of a graph whose deletion yields a disconnected graph with all its components having at least k vertices. To be more precise, we present lower and upper bounds for the k-restricted edge-connectivity of G"m*G"p, and provide sufficient conditions that ensure an optimal value for this parameter. When both G"m and G"p are regular graphs, conditions for guaranteeing that G"m*G"p is [email protected]"("k") are also presented, and the particular case where both G"m and G"p are complete graphs is considered.