{
  "id": "1607.00547",
  "version": "v1",
  "published": "2016-07-02T18:38:27.000Z",
  "updated": "2016-07-02T18:38:27.000Z",
  "title": "On the Automorphism Group of a Graph",
  "authors": [
    "Wenxue Du"
  ],
  "comment": "55 pages, 8 figures",
  "categories": [
    "math.CO"
  ],
  "abstract": "An automorphism of a graph $G$ with $n$ vertices is a bijective map $\\phi$ from $V(G)$ to itself such that $\\phi(v_i)\\phi(v_j)\\in E(G)$ $\\Leftrightarrow$ $v_i v_j\\in E(G)$ for any two vertices $v_i$ and $v_j$ of $G$. Denote by $\\mathfrak{G}$ the group consisting of all automorphisms of $G$. As well-known, the structure of the action of $\\mathfrak{G}$ on $V(G)$ is represented definitely by its block systems. On the other hand for each permutation $\\sigma$ on $[n]$, there is a natural action on any vector $\\pmb{v}=(v_1,v_2,\\ldots,v_n)^t\\in \\mathbb{R}^n$ such that $\\sigma\\pmb{v}=(v_{\\sigma^{-1}1},v_{\\sigma^{-1}2},\\ldots,v_{\\sigma^{-1} n})^t$. Accordingly, we actually have a permutation representation of $\\mathfrak{G}$ in $\\mathbb{R}^n$. In this paper, we establish the some connections between block systems of $\\mathfrak{G}$ and its irreducible representations, and by virtue of that we finally devise an algorithm outputting a generating set and all block systems of $\\mathfrak{G}$ within time $n^{C \\log n}$ for some constant $C$.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2016-07-02T18:38:27.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "05C25",
      "05C50",
      "05C60",
      "05C85"
    ],
    "keywords": [
      "automorphism group",
      "block systems",
      "natural action",
      "permutation representation",
      "connections"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 55,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}