On two algebras of token graphs

M. A. Reyes, C. Dalfó, M. A. Fiol

Published 2024-03-27Version 1

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 $\L_k$ of $F_k(G)$ and the Laplacian matrix $\overline{\L}_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 $\L_k$ and $\overline{\L}_k$ was given in [C. Dalf\'o, F. Duque, R. Fabila-Monroy, M. A. Fiol, C. Huemer, A. L. Trujillo-Negrete, and F. J. Zaragoza Mart\'{\i}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 ${\cal L}(G)$, generated by the pair $(\L_k, \overline{\L}_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 ${\cal A}(n,k)$ that contains ${\cal L}(G)$ together with the Laplacian and adjacency matrices of the $k$-token graph of any graph $G$ on $n$ vertices.