Super Connectivity of Kronecker Products of Some Graphs

Abstract

Let \(G_1\) and \(G_2\) be two connected graphs. The Kronecker product \(G_1 \times G_2\) has vertex set \(V(G_1 \times G_2) = V(G_1) \times V(G_2)\) and the edge set \(E(G_1 \times G_2) = \{(u_1, v_1), (u_2, v_2) : u_1u_2 \in E(G_1), v_1v_2 \in E(G_2)\}\). In this paper, we show that \(K_n \times K_m\) is super-\(\chi\) for \(n \geq m \geq 2\) and \(n+m \geq 5\), \(K_m \times P_n\) is super-\(\kappa\) for \(n \geq m \geq 3\), and \(K_m \times C_n\) is super-\(\kappa\) for \(n \geq m \geq 3\).