With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, tutorials, and more.

No credit card required

1.3 Groups and Graph Spectra

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 PTAP = A or PA = 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 Ã = UTAU be the Jordan form of A, we have (UÃUT)X = X(UÃUT Ã = Ã, where = UTXU.

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 ...

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, interactive tutorials, and more.

No credit card required