On two algebras of token graphs

Abstract

The $k$-token graph $F_k(G)$ of a graph $G$ is the graph whose vertices are the $k$-subsets of vertices from $G$, two of which being adjacent whenever their symmetric difference is a pair of adjacent vertices in $G$. In this article, we describe some properties of the Laplacian matrix ${Ł}_k$ of $F_k(G)$ and the Laplacian matrix ${\overline{Ł}}_k$ of the $k$-token graph $F_k(\overline{G})$ of its complement $\overline{G}$. In this context, a result about the commutativity of the matrices ${Ł}_k$ and ${\overline{Ł}}_k$ was given in [C. Dalfó, F. Duque, R. Fabila-Monroy, M. A. Fiol, C. Huemer, A. L. Trujillo-Negrete, and F. J. Zaragoza Mart\'ınez, On the Laplacian spectra of token graphs, {\em Linear Algebra Appl.} {\bf 625} (2021) 322--348], but the proof was incomplete, and there were some typos. Here, we give the correct proof. Based on this result, and fixed the pair $(n,k)$ and the graph $G$, we first introduce a `local' algebra $\mathcal{L}(G)$, generated by the pair $({Ł}_k,{\overline{Ł}}_k)$, showing its closed relationship with the Bose-Mesner algebra of the Johnson graphs $J(n,k)$. Finally, fixed only $(n,k)$, we present a `global' algebra $\mathcal{A}(n,k)$ that contains $\mathcal{L}(G)$ together with the Laplacian and adjacency matrices of the $k$-token graph of any graph $G$ on $n$ vertices.