The Algebraic Connectivity and Laplacian Spectral Radius of Token Graphs
Abstract
For a graph G=(V,E) of order n and an integer k between $1$ and ⌊n/2⌋, its token graph Fk(G) is the graph whose vertices consist of the binomnk k-subsets of V, and two vertices of Fk(G) are adjacent whenever their symmetric difference is an edge in E. It was found that the algebraic connectivity of a graph is greater than or equal to that of its token graph, while the Laplacian spectral radius of a graph is less than or equal to that of its token graph. Moreover, a conjecture that the algebraic connectivity of a graph coincides with that of its token graph has been proved by using the theory of continuous Markov chains of random walks. In this paper, we derive some results about the algebraic connectivities of a graph and the same graph after adding new edges and their token graphs to obtain a combinatorial/algebraic proof. Besides, we provide some conditions under which the Laplacian spectral radius of a graph is less than that of its token graph. Finally, we characterize the graphs that have the same Laplacian spectral radius as their token graphs, including trees.
Related
- Spectral radius and edge-disjoint spanning trees of graphs with edge connectivity
- Independence number, essential connectivity and the distance spectral radius of graphs
- A solution to a conjecture on the signless Laplacian spectral radius for t-color-critical graphs
- Characterization of graphs attaining the maximum signless Laplacian spectral radius under forbidden cycles and theta graphs
- Connected graphs having maximum signless Laplacian spectral radius
BibTeX
@misc{song2026algebraic,
title = {{The Algebraic Connectivity and Laplacian Spectral Radius of Token Graphs}},
author = {Xiaodi Song and Cristina Dalfó and Miquel Àngel Fiol and Shenggui Zhang},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.00500},
eprint = {2610.00500},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.00500},
note = {CC BY-NC-ND 4.0},
}
RIS
TY - UNPB
TI - The Algebraic Connectivity and Laplacian Spectral Radius of Token Graphs
AU - Xiaodi Song
AU - Cristina Dalfó
AU - Miquel Àngel Fiol
AU - Shenggui Zhang
PY - 2026
DA - 2026/10/01
PB - arXiv
DO - 10.48550/arxiv.2610.00500
UR - https://arxiv.org/abs/2610.00500
AB - For a graph G=(V,E) of order n and an integer k between $1$ and ⌊n/2⌋, its token graph F_k(G) is the graph whose vertices consist of the binomnk k-subsets of V, and two vertices of F_k(G) are adjacent whenever their symmetric difference is an edge in E. It was found that the algebraic connectivity of a graph is greater than or equal to that of its token graph, while the Laplacian spectral radius of a graph is less than or equal to that of its token graph. Moreover, a conjecture that the algebraic connectivity of a graph coincides with that of its token graph has been proved by using the theory of continuous Markov chains of random walks. In this paper, we derive some results about the algebraic connectivities of a graph and the same graph after adding new edges and their token graphs to obtain a combinatorial/algebraic proof. Besides, we provide some conditions under which the Laplacian spectral radius of a graph is less than that of its token graph. Finally, we characterize the graphs that have the same Laplacian spectral radius as their token graphs, including trees.
ER -