2024/02/28 by Ruy Fabila‐Monroy, Fabila-Monroy, Ruy, Sergio Gerardo Gómez-Galicia +5
Computer Science · #05C05 #05C75 #05C76 #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics #Graph Labeling and Dimension Problems #semigroups and automata theory
paper · pdf · doi:10.48550/arxiv.2402.17962
openalex publication_date 2024/02/28 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/01
Let G be a graph on n vertices and 1 ≤ k ≤ n a fixed integer. The k-token graph of G is the graph Fk(G) whose vertex set consists of all k-subsets of the vertex set of G, where two vertices A and B are adjacent in Fk(G) whenever their symmetric difference A\triangle B is an edge of G. In this paper we study the treewidth of Fk(G) when G is a star, path, or a complete graph. We show that in the first two cases, the treewidth is of order Θ(nk-1), and of order Θ(nk) in the third case. We conjecture that our upper bound for the treewidth of Fk(Kn) is tight. This is particularly relevant since Fk(Kn) is isomorphic to the well known Johnson graph J(n,k).