Super-connectivity of Kronecker products of split graphs, powers of cycles, powers of paths and complete graphs (Q1761577)

For a graph \(G\), let \(\kappa(G)\) and \(\delta(G)\) be the connectivity of \(G\) and the minimum degree of \(G\), respectively. A graph \(G\) is called maximally connected if \(\kappa(G)=\delta(G)\). The Kronecker product of two connected graphs \(G_1, G_2\) denoted by \(G_1\times G_2\), is the graph with vertex set \[ V(G_1\times G_2)=V(G_1)\times V(G_2) \] and edge set \[ E(G_1\times G_2)=\{(u_1,v_1)(u_2,v_2): u_1u_2\in E(G_1), v_1v_2\in E(G_2)\}. \] The \(k\)th power \(G^k\) of \(G\) is the graph with vertex set \(V(G)\) such that two distinct vertices are adjacent in \(G^k\) if and only if their distance apart in \(G\) is at most \(k\). A maximally connected graph \(G\) is called super-connected if every minimal vertex cut of \(G\) is the set of neighbors of some vertex in \(G\). A graph \(G=(V,E)\) is called a split graph if \(V\) can be partitioned into a clique \(C\) and an independent set \(I\). For a split graph \(G\), write \(G=(C,I,E)\). In this paper, the authors consider the super-connectivity of the Kronecker products of several kinds of graphs and complete graphs. Their main results are the following. {\parindent=7mm \begin{itemize}\item[(i)]For a split graph \(G=(C,I,E)\) with \(|C|\geq 4\), \(\kappa(G \times K_m)=\delta(G)(m-1)\) for \(m\geq 3\). \item[(ii)]For a non-complete split graph \(G=(C,I,E)\) with \(|C|\geq 5\), \(G\times K_m\) is super-connected, where \(m\geq 3\). \item[(iii)]For \(n\geq 2k+1, m\geq 3\), \(K_m\times P_n^k\) is maximally connected. \end{itemize}}