Increasing the connectivity of split-stars (Q2716670)

Let \(n\geq 3\) be an integer and let \(S_n\) be the symmetric group on \(\{1,2,\ldots,n\}\). The authors define the split-star \(S_n^2\) as the following graph. The vertex set of \(S_n^2\) consists of the \(n!\) permutations in \(S_n\). Two permutations \(g,f\in S_n\) are adjacent if and only if \(g(1,2)=f\), \(g(1,2,i)=f\), or \(g(1,i,2)=f\) for \(i\geq 3\), where \((1,2)\) is a transposition and \((1,2,i)\) and \((1,i,2)\) are 3-cycles. The authors study connectivity properties of this special family of \((2n-3)\)-regular graphs. For example, Theorem 3.2 states: If \(X\) is a set of \(2n-2\) vertices of \(S_n^2\), then \(S_n^2-X\) is either connected or has two components, one of which consists of exactly one vertex.