Some bounds on the Laplacian eigenvalues of token graphs
| Autor: | Dalfó, Cristina, Fiol, Miquel Àngel, Messegué, Arnau |
|---|---|
| Rok vydání: | 2023 |
| Předmět: | |
| Druh dokumentu: | Working Paper |
| Popis: | The $k$-token graph $F_k(G)$ of a graph $G$ on $n$ vertices is the graph whose vertices are the ${n\choose k}$ $k$-subsets of vertices from $G$, two of which being adjacent whenever their symmetric difference is a pair of adjacent vertices in $G$. It is known that the algebraic connectivity (or second Laplacian eigenvalue) of $F_k(G)$ equals the algebraic connectivity $\alpha(G)$ of $G$. In this paper, we give some bounds on the (Laplacian) eigenvalues of a $k$-token graph (including the algebraic connectivity) in terms of the $h$-token graph, with $h\leq k$. For instance, we prove that if $\lambda$ is an eigenvalue of $F_k(G)$, but not of $G$, then $$ \lambda\ge k\alpha(G)-k+1. $$ As a consequence, we conclude that if $\alpha(G)\geq k$, then $\alpha(F_h(G))=\alpha(G)$ for every $h\le k$. Comment: arXiv admin note: text overlap with arXiv:2309.07089 |
| Databáze: | arXiv |
| Externí odkaz: |
|