Next: Regular graphs Up: The spectrum of a Previous: Interlacing

# Automorphisms

An automorphism of a graph is a permutation of its point set such that if and only if . Given , we have a linear transformation on defined by for , . That is an automorphism is expressed by . It follows that preserves the eigenspaces of .

(More generally, if is a group of automorphisms of then we find a linear representation of degree of .)

We denote the group of all automorphisms of by . One would expect that when is large, then tends to be large, so that has only few distinct eigenvalues. And indeed the arguments below will show that a transitive group of automorphisms does not go very well together with simple eigenvalues.

Suppose , say . Since preserves we must have . So either is constant on the orbits of , or has even order, , and is constant on the orbits of . For the Perron-Frobenius eigenvector we are always in the former case.

Corollary 1.6.1   If all eigenvalues are simple, then is an elementary abelian 2-group.

Proof:    If has order larger than two, then there are two distinct vertices , in an orbit of , and all eigenvectors have identical - and -coordinates, contradiction.

Corollary 1.6.2   Let be transitive on . (Then is regular of degree , say.)

1. If for some eigenvalue , then is even, and . If is moreover edge-transitive then is bipartite and .

2. If for two distinct eigenvalues , then .

3. If for all eigenvalues , then has at most two vertices.

Proof:     (i) Suppose . Then induces a partition of into two equal parts: , where for and for . Now for .

(ii) If , then we find 3 pairwise orthogonal -vectors, and a partition of into four equal parts.

(iii) There are not enough integers between and .

For more details, see Cvetkovic, Doob & Sachs [6], Chapter 5.

Next: Regular graphs Up: The spectrum of a Previous: Interlacing
Andries Brouwer 2003-09-30