On the algebraic connectivity of token graphs and graphs under perturbations☆

Given a graph G = (V, E) on n vertices and an integer k between 1 and n-1, the k-token graph Fk(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 (second smallest Laplacian eigenvalues) of G and Fk(G) coincide, but a combinatorial/algebraic proof has been shown elusive. In this paper, we use the latter approach and prove that such equality holds for different new classes of graphs under perturbations, such as 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 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 conditions under which the perturbed graph G + uv, with uv is an element of E, has the same algebraic connectivity as G. (c) 2025 The Author(s). Published by Elsevier B.V. This is an open access article under the CC BY-NC-ND license (http://creativecommons.org/licenses/by-nc-nd/4.0/).