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_1v_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, \min_{j =\lambda}^\delta\{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 \geq \lambda=\lambda (H)\).