{
  "id": "2309.09041",
  "version": "v1",
  "published": "2023-09-16T16:43:14.000Z",
  "updated": "2023-09-16T16:43:14.000Z",
  "title": "Some bounds on the Laplacian eigenvalues of token graphs",
  "authors": [
    "Cristina Dalfó",
    "Miquel Àngel Fiol",
    "Arnau Messegué"
  ],
  "comment": "arXiv admin note: text overlap with arXiv:2309.07089",
  "categories": [
    "math.CO"
  ],
  "abstract": "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$.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2023-09-16T16:43:14.000Z"
    }
  ],
  "analyses": {
    "keywords": [
      "token graph",
      "algebraic connectivity",
      "second laplacian eigenvalue",
      "adjacent vertices",
      "symmetric difference"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 0,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}