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

This work deals with a generalization of the Cartesian product of graphs, the product graph Gm∗GpGm∗Gp 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 kk-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 kk vertices. To be more precise, we present lower and upper bounds for the kk-restricted edge-connectivity of Gm∗GpGm∗Gp, and provide sufficient conditions that ensure an optimal value for this parameter. When both GmGm and GpGp are regular graphs, conditions for guaranteeing that Gm∗GpGm∗Gp is super-λ(k)λ(k) are also presented, and the particular case where both GmGm and GpGp are complete graphs is considered.