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

摘要

The product graph G(m) * G(p) of two given graphs G(m) and G(p) was defined by Bermond et al. [Large graphs with given degree and diameter II, J. Combin. Theory Ser. B 36 (1984) 32-48]. For this kind of graphs we provide bounds for two connectivity parameters (lambda and lambda', edge-connectivity and restricted edge-connectivity, respectively), and state sufficient conditions to guarantee optimal values of these parameters. Moreover, we compare our results with other previous related ones for permutation graphs and cartesian product graphs, obtaining several extensions and improvements. In this regard, for any two connected graphs Gm, Gp of minimum degrees delta(G(m)), delta(G(p)), respectively, we show that lambda(G(m) * G(p)) is lower bounded by both delta(G(m)) + lambda(G(p)) and delta(G(p)) + lambda(G(m)), an improvement of what is known for the edge-connectivity of G(m) x G(p). (c) 2007 Elsevier B.V. All rights reserved.