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$.
Categories: math.CO