Some bounds on the Laplacian eigenvalues of token graphs

Abstract

The $k$-token graph $F_k(G)$ of a graph $G$ on $n$ vertices is the graph whose vertices are the $\left(\genfrac{}{}{0ex}{}{n}{k}\right)$ $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 known that the algebraic connectivity (or second Laplacian eigenvalue) of $F_k(G)$ equals the algebraic connectivity $\alpha (G)$ of $G$. In this paper, we give some bounds on the (Laplacian) eigenvalues of a $k$-token graph (including the algebraic connectivity) in terms of the $h$-token graph, with $h\le k$. For instance, we prove that if $\lambda$ is an eigenvalue of $F_k(G)$, but not of $G$, then $$\lambda \ge k\alpha (G)-k+1.$$ As a consequence, we conclude that if $\alpha (G)\ge k$, then $\alpha (F_h(G))=\alpha (G)$ for every $h\le k$.

arXiv admin note: text overlap with arXiv:2309.07089