Proof of a conjecture on connectivity of Kronecker product of graphs

For a graph G, kappa (G) denotes its connectivity. The Kronecker product G(1) x G(2) of graphs G(1) and G(2) is the graph with the vertex set V(G(1)) x V(G(2)), two vertices (u(1), v(1)) and (u(2), v(2)) being adjacent in G(1) x G(2) if and only if u(1)u(2) is an element of E(G(1)) and v(1)v(2) is an element of E(G(2)). Guji and Vumar [R. Guji, E. Vumar, A note on the connectivity of Kronecker products of graphs, Appl. Math. Lett. 22 (2009) 1360-1363] conjectured that for any nontrivial graph G, kappa(G x K(n)) = min{n kappa (G), (n - 1)delta(G)} when n >= 3. In this note, we confirm this conjecture to be true. (C) 2011 Elsevier B.V. All rights reserved.