Characterizations of Optimal Component Cuts of Locally Twisted Cubes

The k-component connectivity \(c\kappa _{k}(G)\) of a non-complete graph G is the minimum number of nodes whose deletion results in a graph with at least k components. A node subset S of G is called an optimal k-component cut if \(|S|=c\kappa _{k}(G)\) and \(G-S\) has exactly k components. In this paper, we determine the component connectivity of the locally twisted cube \(LTQ_{n}\), i.e. \(c\kappa _{k+1}(LTQ_{n})=kn-k(k+1)/2+1\) for \(1\le k\le n-1\), \(n\ge 2\), and characterize optimal k-component cuts of \(LTQ_{n}\).