Super connectivity of a family of direct product graphs

Abstract

Let $G_1$ and $G_2$ be two 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)\mid u_1{u}_2\in E(G_1),v_1{v}_2\in E(G_2)\}.$ In this paper we show that if $K_{p_1,p_2,\dots ,p_r}$ is a complete multipartite graph, where the parameters $p_1,p_2,\dots ,p_r$ satisfying certain conditions and $P_n$ is a path of length n−1, then $K_{p_1,p_2,\dots ,p_r}\times P_n$ is not super i-connected, where $1\le i\le n-1$ and $n\ge 2$. Also we show that $K_{p_1,p_2,\dots ,p_r}\times C_n$ is not super connected, where $C_n$ is a cycle of length n and $n\ge 3$.

Keywords:

• Direct product
• super connectivity
• separating set

2010 Mathematics Subject Classifications:

• 05C40
• 05C90

Acknowledgments

The authors gratefully appreciate anonymous referees for constructive comments and recommendations which definitely helped to improve the readability and quality of the paper.

Disclosure statement

No potential conflict of interest was reported by the author(s).