Skip to content
Preprint

The Algebraic Connectivity and Laplacian Spectral Radius of Token Graphs

Sep 2026 · 0 citations · 27 references
Mathematics

Abstract

For a graph $G=(V,E)$ of order $n$ and an integer $k$ between $1$ and $\lfloor\frac{n}{2}\rfloor$, its token graph $F_k(G)$ is the graph whose vertices consist of the $\binom{n}{k}$ $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.

View source

Similar papers

Preprint Oct 2026

The domination number of the $k$-token graph of the complete bipartite graph $K_{m,n}$

This paper is about token graphs and domination number. Let $G=(X,E)$ denote an undirected graph that is connected, with no loops or multiple edges, vertex set $X$, and edge set $E$. Pick a positive integer $k\leq \vert X\vert$. The $k$-token graph of $G$, denoted by $F_k(G)$, is defined as follows. The vertex set $\ma...

Nathaniel Chinman, A. Cortijo, Beatrice Pedroni et al. · 1 citation
Preprint Oct 2026

Counting cographs in locally dense graphs

An $n$-vertex graph $G$ is $(\rho, d)$-dense if for all $U \subseteq V(G)$ of size at least $\rho n$, the induced subgraph $G[U]$ contains at least $\frac{d}{2}|U|^2$ edges. In 2010, partly motivated by the theory of quasirandomness, Kohayakawa, Nagle, R\"{o}dl, and Schacht conjectured that, for any fixed graph $F$, th...

Hyunwoo Lee · 0 citations
Preprint Oct 2026

The domination number of the 2-token graph of the complete bipartite graph

For a graph $G$, the $2$-token graph $F_2(G)$ has as vertices all $2$-subsets of $V(G)$, with two such subsets adjacent whenever their symmetric difference is an edge of $G$. In this paper, we determine the domination number of the $2$-token graph of the complete bipartite graph $K_{m,n}$, for all integers $2\le m\le n...

E. Troncoso, I. Caldera, L. M. Rivera · 0 citations
Preprint Sep 2026

Connected graphs with minimum adjacency spectral gap

Let $G$ be a connected graph, and let $\lambda_1(G)>\lambda_2(G)$ denote its two largest adjacency eigenvalues. The spectral gap of $G$ is defined as the difference $\lambda_1(G) - \lambda_2(G)$. For integers $r\geq 2$ and $s\geq 0$, the double kite $DK(r,s)$ is formed by taking two vertex-disjoint copies of the comple...

Le-Le Liu, Michael Tait, Yi Wang · 1 citation
Preprint Aug 2026

The Cayley Completion of a Graph

A finite connected graph is rarely a Cayley graph. We measure how far it is from being one: given $G$ with $n$ vertices and $m$ edges, how few edges must be added, or added and deleted, before the result is a Cayley graph of an abelian group of order $n$ on the same vertex set? This defines two invariants, the completi...

Rigobert Fokam Souop, Laurent Bitjoka · 2 citations · ⚡2
Preprint Aug 2026

On the structure of graphs with given odd girth and large algebraic connectivity

A classical result of Andr\'asfai, Erd\H{o}s, and S\'os states that every $n$-vertex graph with odd girth at least $2k+1$ and minimum degree larger than $\frac{2n}{2k+1}$ is bipartite. Rather than imposing a minimum-degree condition, in this paper we investigate conditions on algebraic connectivity that force graphs of...

Zheng-Bo Chen, Chen-Xing Li, Zhouningxin Wang · 0 citations

We use cookies to run the site and, with your consent, for analytics and to show ads. See our Cookie Policy.