Connectivity of Cartesian product graphs

Use V-i, K-i, lambda(i), delta(i) to denote order, connectivity, edge-connectivity and minimum degree of a graph G(i) for i = 1, 2, respectively. For the connectivity and the edge-connectivity of the Cartesian product graph, up to now, the best results are K(G(1) x G(2)) >= K-1 + K-2 and (G(1) x G(2)) >= k(1) + k(2). This paper improves these results by proving that K(G(1) x G(2)) >= min {k(1) + delta(2), k(2) + delta(1)} and lambda(G(1) x G(2)) = min {delta(1) +delta(2) lambda(1) v(2), lambda(2) v(1)} if G(1) and G(2) are connected undirected graphs; K(G(1) x G(2)) >, min {k(1) + delta(2), k(2) + delta(1), 2K(1) + K-2, 2K(2) + K-1} if G(1) and G(2) are strongly connected digraphs. These results are also generalized to the Cartesian products of n (>= 3) connected graphs and n strongly connected digraphs, respectively. (c) 2005 Elsevier B.V. All rights reserved.