{
  "id": "2207.12336",
  "version": "v2",
  "published": "2022-07-25T16:53:07.000Z",
  "updated": "2022-07-28T21:14:55.000Z",
  "title": "Connected ($C_4$,Diamond)-free Graphs Are Uniquely Reconstructible from Their Token Graphs",
  "authors": [
    "Ruy Fabila-Monroy",
    "Ana Laura Trujillo-Negrete"
  ],
  "categories": [
    "math.CO"
  ],
  "abstract": "A diamond is the graph that is obtained from removing an edge from the complete graph on $4$ vertices. A ($C_4$,diamond)-free graph is a graph that does not contain a diamond or a cycle on four vertices as induced subgraphs. Let $G$ be a connected ($C_4$,diamond)-free graph on $n$ vertices. Let $1 \\le k \\le n-1$ be an integer. The $k$-token graph, $F_k(G)$, of $G$ is the graph whose vertices are all the sets of $k$ vertices of $G$; two of which are adjacent if their symmetric difference is a pair of adjacent vertices in $G$. Let $F$ be a graph isomorphic to $F_k(G)$. In this paper we show that given only $F$, we can construct in polynomial time a graph isomorphic to $G$. Let $\\operatorname{Aut}(G)$ be the automorphism group of $G$. We also show that if $k\\neq n/2$, then $\\operatorname{Aut}(G) \\simeq \\operatorname{Aut}(F_k(G))$; and if $k = n/2$, then $\\operatorname{Aut}(G) \\simeq \\operatorname{Aut}(F_k(G)) \\times \\mathbb{Z}_2$.",
  "revisions": [
    {
      "version": "v2",
      "updated": "2022-07-28T21:14:55.000Z"
    }
  ],
  "analyses": {
    "keywords": [
      "token graph",
      "uniquely reconstructible",
      "graph isomorphic",
      "complete graph",
      "adjacent vertices"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 0,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}