On the super connectivity of direct product of graphs

¹ Department of Mathematics, Urmia University, Urmia 57135, Iran
² Department of Mathematics, Khoy Branch, Islamic Azad University, Khoy 58168-44799, Iran

^* Corresponding author: m.ghasemi@urmia.ac.ir, math.ghasemi@gmail.com

Received: 15 December 2021
Accepted: 24 May 2022

Abstract

A vertex-cut S is called a super vertex-cut if G − S is disconnected and it contains no isolated vertices. The super-connectivity, κ′, is the minimum cardinality over all super vertex-cuts. This article provides bounds for the super connectivity of the direct product of an arbitrary graph and the complete graph K_n. Among other results, we show that if G is a non-complete graph with girth(G) = 3 and κ′(G) = ∞, then κ′(G × K_n) ≤ min{mn − 6, m(n − 1) + 5, 5n + m − 8}, where |V(G)| = m.