On the algebraic connectivity of token graphs

2022/09/02 by Dalfó, C., Fiol, M. A.
#05C10 #05C15 #05C50 #Combinatorics (math.CO) #FOS: Mathematics

paper · doi:10.48550/arxiv.2209.01030

Abstract

We study the algebraic connectivity (or second Laplacian eigenvalue) 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. Recently, it was conjectured that the algebraic connectivity of F_k(G) equals the algebraic connectivity of G. In this paper, we prove the conjecture for new infinite families of graphs, such as trees and graphs with maximum degree large enough.

Related

• On the spectra of token graphs of cycles and other graphs
• Some bounds on the Laplacian eigenvalues of token graphs
• On the Laplacian spectra of token graphs
• On the Algebraic Connectivity of Token Graphs and Graphs under Perturbations
• The Edge-connectivity of Token Graphs