On the Automorphism Group of a Graph

Abstract

An automorphism of a graph $G$ with $n$ vertices is a bijective map $\varphi$ from $V(G)$ to itself such that $\varphi (v_i)\varphi (v_j)\in E(G)$ $\iff$ $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 $v=(v_1,v_2,\dots ,v_n{)}^t\in {\mathbb{R}}^n$ such that $\sigma v=(v_{{\sigma }^{-1}1},v_{{\sigma }^{-1}2},\dots ,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$.

55 pages, 8 figures

References in corpus (1)

• Practical graph isomorphism, II