{
  "id": "1511.07268",
  "version": "v1",
  "published": "2015-11-23T15:21:44.000Z",
  "updated": "2015-11-23T15:21:44.000Z",
  "title": "Automorphism groups of Cayley graphs generated by block transpositions and regular Cayley maps",
  "authors": [
    "Annachiara Korchmaros",
    "István Kovács"
  ],
  "categories": [
    "math.CO",
    "math.GR"
  ],
  "abstract": "This paper deals with the Cayley graph $\\mathrm{Cay}(\\mathrm{Sym}_n,T_n),$ where the generating set consists of all block transpositions. A motivation for the study of these particular Cayley graphs comes from current research in Bioinformatics. As the main result, we prove that Aut$(\\mathrm{Cay}(\\mathrm{Sym}_n,T_n))$ is the product of the left translation group by a dihedral group $\\mathsf{D}_{n+1}$ of order $2(n+1)$. The proof uses several properties of the subgraph $\\Gamma$ of $\\mathrm{Cay}(\\mathrm{Sym}_n,T_n)$ induced by the set $T_n$. In particular, $\\Gamma$ is a $2(n-2)$-regular graph whose automorphism group is $\\mathsf{D}_{n+1},$ $\\Gamma$ has as many as $n+1$ maximal cliques of size $2,$ and its subgraph $\\Gamma(V)$ whose vertices are those in these cliques is a $3$-regular, Hamiltonian, and vertex-transitive graph. A relation of the unique cyclic subgroup of $\\mathsf{D}_{n+1}$ of order $n+1$ with regular Cayley maps on $\\mathrm{Sym}_n$ is also discussed. It is shown that the product of the left translation group by the latter group can be obtained as the automorphism group of a non-$t$-balanced regular Cayley map on $\\mathrm{Sym}_n$.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2015-11-23T15:21:44.000Z"
    }
  ],
  "analyses": {
    "keywords": [
      "automorphism group",
      "block transpositions",
      "left translation group",
      "balanced regular cayley map",
      "cayley graphs comes"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 0,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}