| Article ID | Journal | Published Year | Pages | File Type |
|---|---|---|---|---|
| 4651273 | Discrete Mathematics | 2006 | 7 Pages |
Use vi,κi,λi,δivi,κi,λi,δi to denote order, connectivity, edge-connectivity and minimum degree of a graph GiGi for i=1,2i=1,2, respectively. For the connectivity and the edge-connectivity of the Cartesian product graph, up to now, the best results are κ(G1×G2)⩾κ1+κ2κ(G1×G2)⩾κ1+κ2 and λ(G1×G2)⩾λ1+λ2λ(G1×G2)⩾λ1+λ2. This paper improves these results by proving that κ(G1×G2)⩾min{κ1+δ2,κ2+δ1}κ(G1×G2)⩾min{κ1+δ2,κ2+δ1} and λ(G1×G2)=min{δ1+δ2,λ1v2,λ2v1}λ(G1×G2)=min{δ1+δ2,λ1v2,λ2v1} if G1G1 and G2G2 are connected undirected graphs; κ(G1×G2)⩾min{κ1+δ2,κ2+δ1,2κ1+κ2,2κ2+κ1}κ(G1×G2)⩾min{κ1+δ2,κ2+δ1,2κ1+κ2,2κ2+κ1} if G1G1 and G2G2 are strongly connected digraphs. These results are also generalized to the Cartesian products of n(⩾3) connected graphs and n strongly connected digraphs, respectively.
