The super edge connectivity of Kronecker product graphs

Department of Mathematics, Ege University Bornova, Izmir 35100, Turkey.

^a Corresponding author: gulnaz.boruzanli@ege.edu.tr

Received: 10 August 2016
Accepted: 13 October 2017

Abstract

Let G₁ and G₂ be two graphs. The Kronecker product G₁ × G₂ has vertex set V (G₁ × G₂) = V (G₁) × V (G₂) and edge set E(G₁ × G₂) = {(u₁, v₁)(u₂, v₂) : u₁u₂ ∈ E(G₁) and v₁v₂ ∈ E(G₂)}. In this paper we determine the super edge–connectivity of G × K_n for n ≥ 3. More precisely, for n ≥ 3, if λ′(G) denotes the super edge–connectivity of G, then at least min{n(n-1)λ′(G), min_xy∈E(G){deg_G(x)+deg_G(y)}(n-1)-2} edges need to be removed from G × K_n to get a disconnected graph that contains no isolated vertices.