×

On the connectivity of the direct product of graphs. (English) Zbl 1170.05041

Summary: In this note we show that the edge-connectivity \(\lambda(G\times H)\) of the direct product of graphs \(G\) and \(H\) is bounded below by \(\min\{\lambda(G)|E(H)|, \lambda(H)|E(G)|, \delta(G\times H)\}\) and above by \(\min\{2\lambda(G)|E(H)|, 2\lambda(H)|E(G)|, \delta(G\times H)\}\) except in some special cases when \(G\) is a relatively small bipartite graph, or both graphs are bipartite. Several upper bounds on the vertex-connectivity of the direct product of graphs are also obtained.

MSC:

05C40 Connectivity
PDFBibTeX XMLCite