Restricted connectivity for some interconnection networks (Q497373): Difference between revisions

This paper studies restricted connectivity and super connectivity of a connected graph \(G\). A vertex-cut \(S\subseteq G\) is called restricted if there is no vertex \(v\in G\), whose neighborhood is contained in \(S\). The restricted connectivity \(\kappa^\prime(G)\) is defined as the order of a minimum restricted vertex-cut in the graph. A vertex-cut is called a super vertex-cut if \(G-S\) contains no isolated vertices. The super connectivity \(\kappa_1(G)\) is defined as the order of a minimum super vertex-cut in \(G\). It is well known that \(\kappa_1(G)\leq\kappa^\prime(G)\). Among other things, the authors prove that \(\kappa_1(K_m\times G_2)=\kappa^\prime(K_m\times G_2)=2k_2+m-2\), where \(G_2\) is a \(k_2 (\geq2)\)-regular and maximally connected graph with girth \(g(G_2)\geq 4\); and \(\kappa_1(G_1\times G_2)=\kappa^\prime(G_1\times G_2)=2(k_1+k_2-1)\), where \(G_i\) is a \(k_i(\geq2)\)-regular and maximally connected graph with girth \(g(G_i)\geq4\) for \(i=1,2\).