The Edge-Connectivity of Token Graphs

Let G be a simple graph of order n≥ 2 and let k∈ { 1 , … , 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 2018 Leaños and Trujillo-Negrete proved that if G is t-connected and t≥ k, then F_k(G) is at least k(t- k+ 1) -connected. In this paper we show that such a lower bound remains true in the context of edge-connectivity. Specifically, we show that if G is t-edge-connected and t≥ k, then F_k(G) is at least k(t- k+ 1) -edge-connected. We also provide some families of graphs attaining this bound.