Connectivity and Edge-Connectivity of Cartesian Products of Graphs
Jun-Ming Xu and Chao Yang
Department of Mathematics, University of Science and Technology of China, Hefei 230026,
P.R. China
Abstract Full Text PDF
The earliest study on
connectivity of Cartesian product graphs can be traced back to
1957 by G. Sabidussi. He proved $\kappa(G_1\times G_2)\geqslant
\kappa(G_1)+\kappa(G_2)$, hence determined the connectivity of
Cartesian product of two maximally connected graphs. This result
was generalized by Xu[1998] and some other authors. Our recent
work determined the exact value of connectivity and
edge-connectivity of Cartesian product of two arbitrary digraphs,
in terms of the parameters of the two factor graphs.
|
|
