
























The $k$-th token graph of a graph $G=(V,E)$ is the graph $F_k(G)$ whose vertices are the $k$-subsets of $V$ and whose edges are all pairs of $k$-subsets $A,B$ such that the symmetric difference of $A$ and $B$ forms an edge in $G$. Let $L(G)$ be the Laplacian matrix of $G$, and $L_k(G)$ be the Laplacian matrix of $F_k(G)$. It was shown by Dalfó et al. that for any graph $G$ on $n$ vertices and any $0\leq \ell \leq k \leq \left\lfloor n/2\right\rfloor$, the spectrum of $L_{\ell}(G)$ is contained in that of $L_k(G)$. Here, we continue to study the relation between the spectrum of $L_k(G)$ and that of $L_{k-1}(G)$. In particular, we show that, for $1\leq k\leq \left\lfloor n/2\right\rfloor$, any eigenvalue $λ$ of $L_k(G)$ that is not contained in the spectrum of $L_{k-1}(G)$ satisfies \[ k(λ_2(L(G))-k+1)\leq λ\leq kλ_n(L(G)), \] where $λ_2(L(G))$ is the second smallest eigenvalue of $L(G)$ (a.k.a. the algebraic connectivity of $G$), and $λ_n(L(G))$ is its largest eigenvalue. Our proof relies on an adaptation of Garland's method, originally developed for the study of high-dimensional Laplacians of simplicial complexes.
此内容由惯性聚合(RSS阅读器)自动聚合整理,仅供阅读参考。 原文来自 — 版权归原作者所有。