Coloquio Queretano de Matemáticas

Given a graph $G=(V,E)$ on $n$ vertices and an integer $k$ between 1 and $n-1$, the $k$-token graph $F_k(G)$ has vertices representing the $k$-subsets of $V$, and two vertices are adjacent if their symmetric difference is the two end-vertices of an edge in $E$. Using the theory of Markov chains of random walks and the interchange process, it was proved that the algebraic connectivities (the second-smallest Laplacian eigenvalues) of $G$ and $F_k(G)$ coincide; however, a combinatorial/algebraic proof is elusive for all graphs. 
In this talk, we employ the latter approach and prove that such an equality holds for various new classes of graphs under perturbations, including extended cycles, extended complete bipartite graphs, kite graphs, and graphs with a cut clique.
Kite graphs are formed by a graph (head) with several paths (tail) rooted at the same vertex and with exciting properties. For instance, we show that the different eigenvalues of a kite graph are also the eigenvalues of its perturbed graph obtained by adding edges.
Moreover, as a particular case of one of our theorems, we generalize a recent result of Barik and Verma (2024) about graphs with a cut vertex of degree $n-1$. 
Along the way, we give the conditions under which the perturbed graph $G+uv$, with $uv\in E$, has the same algebraic connectivity as $G