2023/10/25 by Miguel Reyes, Reyes, M. A., C. Dalfó +3 · 1 citation
Mathematics · #Combinatorics (math.CO) #FOS: Mathematics #Finite Group Theory Research #Graph theory and applications
paper · pdf · doi:10.48550/arxiv.2310.16929
openalex publication_date 2023/10/25 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Let G be a graph on n vertices. The k-token graph (or symmetric k-th power) of G, denoted by Fk(G) has as vertices the n\choose k k-subsets of vertices from G, and two vertices are adjacent when their symmetric difference is a pair of adjacent vertices in G. In particular, Fk(Kn) is the Johnson graph J(n,k), which is a distance-regular graph used in coding theory. In this paper, we present some results concerning the (adjacency and Laplacian) spectrum of Fk(G) in terms of the spectrum of G. For instance, when G is walk-regular, an exact value for the spectral radius ρ (or maximum eigenvalue) of Fk(G) is obtained. When G is distance-regular, other eigenvalues of its 2-token graph are derived using the theory of equitable partitions. A generalization of Aldous' spectral gap conjecture (which is now a theorem) is proposed.