2016/07/02 by Wenxue Du, Du, Wenxue
Computer Science · Mathematics · #05C25 #05C50 #05C60 #05C85 #Coding theory and cryptography #Combinatorics (math.CO) #FOS: Mathematics #Finite Group Theory Research #Graph theory and applications
paper · pdf · doi:10.48550/arxiv.1607.00547
openalex publication_date 2016/07/02 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
An automorphism of a graph G with n vertices is a bijective map ϕ from V(G) to itself such that ϕ(vi)ϕ(vj)∈ E(G) ⇔ vi vj∈ E(G) for any two vertices vi and vj of G. Denote by \mathfrakG the group consisting of all automorphisms of G. As well-known, the structure of the action of \mathfrakG on V(G) is represented definitely by its block systems. On the other hand for each permutation σ on [n], there is a natural action on any vector \pmbv=(v1,v2,…,vn)t∈ ℝn such that σ\pmbv=(vσ-11,vσ-12,…,vσ-1 n)t. Accordingly, we actually have a permutation representation of \mathfrakG in ℝn. In this paper, we establish the some connections between block systems of \mathfrakG and its irreducible representations, and by virtue of that we finally devise an algorithm outputting a generating set and all block systems of \mathfrakG within time nC log n for some constant C.