Let *G* = (*V*, *E*) be a graph with vertex set *V* of size *n*, edge set *E* of size *m*, and automorphism group *Aut*(*G*). (See [3] for general coverage of algebraic aspects of graph theory and [12] for specific treatment of the automorphism group of a graph.) Since automorphisms are in effect relabelings of the vertices, they can be represented as permutation matrices. Let *A* = *A*(*G*) be the adjacency matrix of *G*. Then a permutation matrix *P* is an automorphism of *G* if and only if *P ^{T}AP* =

Thus, one way to construct the automorphism group of a graph *G* is to solve the matrix equation *AX* = *XA* for permutation matrices *X*. The Jordan canonical form of *A* as a matrix over the reals can be used to obtain the general solution *X*. Taking *G* to be undirected and thus *A* symmetric and letting *Ã* = *U ^{T}AU* be the Jordan form of

Thus the construction of *Aut*(*G*) requires computing the orthogonal matrix *U* and finding all that commute with *Ã*. The matrix depends on the elementary divisors of *A*. With no additional information, this method ...

Start Free Trial

No credit card required