2019/09/15 by Jesús Leaños, Leaños, J., Christophe Ndjatchi +1
Biochemistry, Genetics and Molecular Biology · Computer Science · #05C40 #Advanced Graph Theory Research #Advanced biosensing and bioanalysis techniques #Combinatorics (math.CO) #FOS: Mathematics #Interconnection Networks and Systems
paper · pdf · doi:10.48550/arxiv.1909.06698
openalex publication_date 2019/09/15 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Let G be a simple graph of order n≥ 2 and let k∈ \1,… ,n-1\. The k-token graph Fk(G) of G is the graph whose vertices are the k-subsets of V(G), where two vertices are adjacent in Fk(G) whenever their symmetric difference is an edge of G. In 2018 J. Leaños and A. L. Trujillo-Negrete proved that if G is t-connected and t≥ k, then Fk(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 Fk(G) is at least k(t-k+1)-edge-connected. We also provide some families of graphs attaining this bound.