On the Automorphism Group of a Graph

Abstract: An automorphism of a graph

G

with

n

vertices is a bijective map

p h i

from

V (G)

to itself such that

p h i (v_{i}) p h i (v_{j}) i n E (G)

L e f t r i g h t a r r o w

v_{i} v_{j} i n E (G)

for any two vertices

v_{i}

and

v_{j}

of

G

. Denote by

m a t h f r a k G

the group consisting of all automorphisms of

G

. As well-known, the structure of the action of

m a t h f r a k G

on

V (G)

is represented definitely by its block systems. On the other hand for each permutation

s i g m a

on

[n]

, there is a natural action on any vector

p m b v = (v_{1}, v_{2}, l d o t s, v_{n})^{t} i n m a t h b b R^{n}

such that

s i g m a p m b v = (v_{s i g m a^{- 1} 1}, v_{s i g m a^{- 1} 2}, l d o t s, v_{s i g m a^{- 1} n})^{t}

. Accordingly, we actually have a permutation representation of

m a t h f r a k G

in

m a t h b b R^{n}

. In this paper, we establish the some connections between block systems of

m a t h f r a k G

and its irreducible representations, and by virtue of that we finally devise an algorithm outputting a generating set and all block systems of

m a t h f r a k G

within time

n^{C l o g n}

for some constant

C

.

This page was built for publication: On the Automorphism Group of a Graph