{
  "id": "2403.18800",
  "version": "v1",
  "published": "2024-03-27T17:46:11.000Z",
  "updated": "2024-03-27T17:46:11.000Z",
  "title": "On two algebras of token graphs",
  "authors": [
    "M. A. Reyes",
    "C. Dalfó",
    "M. A. Fiol"
  ],
  "categories": [
    "math.CO"
  ],
  "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 $\\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.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2024-03-27T17:46:11.000Z"
    }
  ],
  "analyses": {
    "keywords": [
      "token graph",
      "laplacian matrix",
      "linear algebra appl",
      "adjacent vertices",
      "johnson graphs"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 0,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}