Laplacian spectral radius and integrality of token graphs

Abstract

Let $G$ be a simple graph on $n$ vertices. A graph is a cograph if and only if it contains no induced path on four vertices. The $k$-token graph $F_k(G)$ of $G$ is the graph whose vertices are the $k$-subsets of $V(G)$, and two of them are adjacent whenever their symmetric difference is a pair of adjacent vertices in $G$. It is known that the algebraic connectivity (the second smallest Laplacian eigenvalue) of $G$ is equal to that of $F_k(G)$. Motivated by this, Barik and Verma [Linear Algebra Appl., 687:181--206, (2024)] posed the following question: for which graphs does the Laplacian spectral radius $\rho_L(G)$ (the largest Laplacian eigenvalue) of $G$ equal the Laplacian spectral radius $\rho_L(F_k(G))$ of $F_k(G)$? In this article, we answer this question by proving that $\rho_L(F_k(G))=\rho_L(G)$ if and only if $G$ is a star graph. We also ask the following question: if $G$ is Laplacian integral (all its Laplacian eigenvalues are integers) on $n$ vertices, then is $F_k(G)$ also Laplacian integral for any integer $k$ such that $2\leq k\leq \frac{n}{2}$? We prove that this is not true in general by proving that $F_k(K_n\otimes K_2)$ is not Laplacian integral for $n\geq 3$ and $2\leq k\leq n$, even though $K_n\otimes K_2$ itself is Laplacian integral. Here, $K_n\otimes K_2$ denotes the Kronecker product of graphs $K_n$ and $K_2$. Interestingly, we prove that the token graphs of cographs are Laplacian integrals, thereby showing that the token graph operation can generate new Laplacian integral graphs.