Connectivity of Lexicographic Product and Direct Product of Graphs

Abstract

In this paper, we prove that the connectivity and the edge connectivity of the lexicographic product of two graphs $G_1$ and $G_2$ are equal to ${\kappa }_1{v}_2$ and $min\{{\lambda }_1{v}_2^2,{\delta }_2+{\delta }_1{v}_2\}$, respectively, where ${\delta }_i$, ${\kappa }_i$, ${\lambda }_i$, and $n_i$ denote the minimum degree, connectivity, edge-connectivity, and number of vertices of $G_i$, respectively.
We also obtain that the edge-connectivity of the direct product of $K_2$ and a graph $H$ is equal to $min\{2\lambda ,2\beta ,\underset{j=\lambda }{\overset{\delta }{min}}\{j+2{\beta }_j\}\}$, where $\theta$ is the minimum size of a subset $F\subset E(H)$ such that $H–F$ is bipartite and ${\beta }_j=min\{\beta (C)\}$, where $C$ takes over all components of $H–B$ for all edge-cuts $B$ of size $j\ge \lambda =\lambda (H)$.