The edge-connectivity of token graphs (Q2045395)

Let \(G\) be a simple graph of order \(n\geq 2\) and let \(k\in \{1,\ldots,n-1\}\). The \(k\)-token graph \(F_k(G)\) of \(G\) is the graph whose vertices are the \(k\)-subsets of \(V(G)\), where two vertices are adjacent in \(F_k(G)\) whenever their symmetric difference is an edge of \(G\). In this paper, the authors prove that if \(G\) is \(t\)-edge-connected and \(t\geq k\), then \(F_k(G)\) is \(k(t-k+1)\)-edge-connected. They also provide some constructions showing the sharpness on the edge-connectivity of \(F_k(G)\) in this result.