Super connectivity of Kronecker product of complete bipartite graphs and complete graphs

Let G(1) and G(2) be two graphs. The Kronecker product G(1) x G(2) has vertex set V(G(1) x G(2)) = V(G(1)) x V(G(2)) and edge set E(G(1) x G(2)) = {(u(1), v(1))(u(2), v(2)) : u(1)u(2) epsilon E(G(1)) and v(1)v(2) epsilon E(G(2))}. In this paper we determine that the super-connectivity of K-m,K-r x K-n for n >= 3 is (n = 2)(m + r). That is, for n >= 3, m >= 1 and r >= 1, at least (n - 2)(m + r) vertices need to be removed to get a disconnected graph that contains no isolated vertices. We also determine that the super-connectivity of K-m x K-n is mn - 4, where n >= m >= 2 and n >= 3. We generalize our result by establishing the h-extra-connectivity of K-m,K-r x K-n, for n >= 3, where 1 <= h <= m + r - 1. More precisely we show that the smallest number of vertices that need to be removed from K-m,K-r x K-n so that the resulting graph is disconnected and each component has more than h vertices is (n - 2)(m + r). (C) 2015 Elsevier B.V. All rights reserved.