×

Connectivity of Cartesian product graphs. (English) Zbl 1085.05042

Let \(n(G)\), \(\kappa(G)\), \(\lambda(G)\) and \(\delta(G)\) be the order, connectivity, edge-connectivity and minimum degree of a (di-)graph, respectively. In addition, let \(G_1\times G_2\) be the Cartesian product of two (di-)graphs \(G_1\) and \(G_2\). If \(G_1,G_2\) are two connected graphs, then the authors prove that \(\kappa(G_1\times G_2)\geq\min\{\kappa(G_1)+\delta(G_2), \kappa(G_2)+\delta(G_1)\}\) and \(\lambda(G_1\times G_2)= \min\{\delta(G_1)+\delta(G_2),\lambda(G_1)n(G_2), \lambda(G_2)n(G_1)\}\) when \(G_i\neq K_1\) for \(i=1,2\). In the case that \(G_1,G_2\) are two strongly connected digraphs, it is shown that \(\kappa(G_1\times G_2)\geq\min\{\kappa(G_1)+\delta(G_2), \kappa(G_2)+\delta(G_1),2\kappa(G_1)+\kappa(G_2), 2\kappa(G_2)+\kappa(G_1)\}\). These results are also generalized to the Cartesian product of \(p\geq 3\) (di-)graphs.

MSC:

05C40 Connectivity
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Chiue, W.-S.; Shieh, B.-S., On connectivity of the Cartesian product of two graphs, Applied Math. and Computation, 102, 129-137 (1999) · Zbl 0927.05048
[2] Day, K.; Al-Ayyoub, A.-E., The cross product of interconnection networks, IEEE Trans. Parallel and Distributed Systems, 8, 2, 109-118 (1997)
[3] Dirac, G. A., Généralisations du théorém de Menger, C. R. Acad. Sci. Pairs, 250, 4252-4253 (1960) · Zbl 0095.37803
[4] Sabidussi, G., Graphs with given group and given graph-theoretical properties, Canad. J. Math., 9, 515-525 (1957) · Zbl 0079.39202
[5] Xu, J.-M., Connectivity of Cartesian Product Digraphs and Fault-Tolerant Routings of Generalized Hypercubes, Applied Math. J. Chinese Univ., 13B, 2, 179-187 (1998) · Zbl 0911.05032
[6] Xu, J.-M., Topological Structure and Analysis of Interconnection Networks (2001), Kluwer Academic Publishers: Kluwer Academic Publishers Dordrecht/ Boston/London · Zbl 1046.68026
[7] Xu, J.-M., Theory and Application of Graphs (2003), Kluwer Academic Publishers: Kluwer Academic Publishers Dordrecht/Boston/London
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.