Search

Let G be a simple graph of order $$n\ge 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 2018 Leanos and Trujillo-Negrete proved that if G is t-connected and $$t\ge 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\ge k$$ , then $$F_k(G)$$ is at least $$k(t-k+1)$$ -edge-connected. We also provide some families of graphs attaining this bound.

Let G be a simple graph of order n 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 2012 Fabila et al. conjectured that if G is t-connected and $$t\ge k$$ , then $$F_k(G)$$ is $$k(t-k+1)$$ -connected. In this paper we prove this conjecture.