Algebraic Graph Theory Seminar - Cristina Dalfó

Title: On the Laplacian spectra of token graphs

Abstract:

We study the Laplacian spectrum of token graphs, also called symmetric powers of graphs. The k-token graph F_k(G)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. In this talk, we give a relationship between the Laplacian spectra of any two token graphs of a given graph. In particular, we show that, for any integers such that 1 ≤h ≤k≤n2, the Laplacian spectrum of Fh(G)is contained in the Laplacian spectrum of Fk(G). Besides, we obtain a relationship between the spectra of the k-token graph of G and the k-token graph of its complement. This generalizes to tokens graphs a well-known property stating that the Laplacian eigenvalues of G are closely related to the Laplacian eigenvalues of the complement of G. Finally, we conjecture that the algebraic connectivities of the original graph and its k-token graph coincide.