On connectivity of the cartesian product of two graphs. (English) Zbl 0927.05048

A graph \(G=(V,E)\) is maximum vertex-connected (maximum edge-connected) if its vertex-connectivity (edge-connectivity) equals \(\Bigl\lfloor \tfrac{2| E| }{| V| }\Bigr\rfloor \). Sufficient conditions for the cartesian product of two graphs to be maximum vertex-connected (maximum edge-connected) are given.
Reviewer: P.Horák (Safat)


05C40 Connectivity
05C75 Structural characterization of families of graphs
Full Text: DOI


[1] Yang, C. S.; Wang, J. F.; Lee, J. Y.; Boesch, F. T., Graph theoretic reliability analysis for the Boolean \(n\)-cube networks, IEEE Trans. Circuits Systems, CAS-35, 9, 1175-1179 (1988) · Zbl 0656.94027
[2] Yang, C. S.; Wang, J. F.; Lee, J. Y.; Boesch, F. T., The number of spanning trees of the regular networks, Inter. J. Comput. Math., 23, 185-200 (1988) · Zbl 0683.05016
[3] Lesniak, L., Results on the edge-connectivity of graphs, Discrete Math., 8, 351-354 (1974) · Zbl 0277.05123
[4] Volkmann, L., Edge-connectivity in \(p\)-partite graphs, J. Graph Theory, 13, 1, 1-6 (1989) · Zbl 0800.05008
[5] Boland, J. W.; Ringeisen, R. D., On super \(i\)-connected graphs, Networks, 24, 225-232 (1994) · Zbl 0805.05047
[6] Fàbrega, J.; Fiol, M. A., Maximally connected digraphs, J. Graph Theory, 13, 657-668 (1989) · Zbl 0688.05029
[7] Soneoka, T.; Nakada, H.; Imase, M., Sufficient conditions for maximally connected dense graphs, Discrete Math., 63, 53-66 (1987) · Zbl 0609.05050
[8] Fiol, M. A., The super connectivity of large digraphs and graphs, Discrete Math., 124, 67-78 (1994) · Zbl 0791.05068
[9] Fiol, M. A., On super-edge connected digraphs and bipartite digraphs, J. Graph Theory, 16, 6, 545-555 (1992) · Zbl 0769.05062
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.