On the algebraic connectivity of some token graphs

Abstract The k -token graph Fₖ (G) F k (G) of a graph G is the graph whose vertices are the k -subsets of vertices from G, two of which are adjacent whenever their symmetric difference is a pair of adjacent vertices in G. It was proved that the algebraic connectivity of Fₖ (G) F k (G) equals the algebraic connectivity of G with a proof using random walks and interchange of processes on a weighted graph. However, no algebraic or combinatorial proof is known, and it would be a hit in the area. In this paper, we algebraically prove that the algebraic connectivity of Fₖ (G) F k (G) equals the one of G for new infinite families of graphs, such as trees, some graphs with hanging trees, and graphs with minimum degree large enough. Some examples of these families are the following: the cocktail party graph, the complement graph of a cycle, and the complete multipartite graph.