The generalized 3-connectivity of Cayley graphs on symmetric groups generated by trees and cycles (Q1684938)

Let \(G=(V,E)\) be a graph and \(S\) be a subset of \(V\) of at least two vertices. Let \(\kappa(G,S)\) be the maximum number \(r\) of edge-disjoint trees \(T_1,T_2,\ldots,T_r\) in \(G\) such that \(V(T_i)\cap V(T_j)=S\) for any pair of distinct integers \(i\), \(j\), where \(1\leq i\), \(j\leq r\). For any integer \(p\geq2\), the generalized \(p\)-connectivity \(\kappa_p(G)\) of \(G\), is determined from equality \[ \kappa_p(G)=\min\{\kappa(G,S)\mid S\subset V\text{ and }|S|=p\}. \] This concept was introduced by \textit{M. Hager} [J. Combin. Theory Ser. B 38, No. 2, 179--189 (1985; Zbl 0542.05042)]. Clearly, \(\kappa_2(G)=\kappa(G)\).\newline Let \(\mathcal{T}\) be a set of transpositions of \(\mathrm{Sym}(n)\). The transposition graph of \(\mathcal{T}\), denoted by \(G(\mathcal{T})\), is the graph with vertex set \(\{1,\ldots,n\}\), and with vertices \(i\) and \(j\) being adjacent in \(G(\mathcal{T})\) whenever \((i,j)\in\mathcal{T}\). The following two assertions are proved in this paper:\newline 1) If \(G(\mathcal{T})\) is a tree, then \(\kappa_3(\mathrm{Cay}(\mathrm{Sym}(n),\mathcal{T}))=n-2\).\newline 2) If \(G(\mathcal{T})\) is a cycle, then \(\kappa_3(\mathrm{Cay}(\mathrm{Sym}(n),\mathcal{T}))=n-1\).