On the spectra of token graphs of cycles and other graphs

© 2023 Elsevier. This manuscript version is made available under the CC-BY-NC-ND 4.0 license http://creativecommons.org/licenses/by-nc-nd/4.0
The k-token graph of a graph G is the graph whose vertices are the k-subsets of vertices from G, two of which being adjacent whenever their symmetric difference is a pair of adjacent vertices in G. It is a known result that the algebraic connectivity (or second Laplacian eigenvalue) of equals the algebraic connectivity of G. In this paper, we first give results that relate the algebraic connectivities of a token graph and the same graph after removing a vertex. Then, we prove the result on the algebraic connectivity of 2-token graphs for two infinite families: the odd graphs for all r, and the multipartite complete graphs for all In the case of cycles, we present a new method that allows us to compute the whole spectrum of . This method also allows us to obtain closed formulas that give asymptotically exact approximations for most of the eigenvalues of .
Peer Reviewed
Postprint (author's final draft)