# The ICICS/CS Reading Room

## UBC CS TR-77-18 Summary

- No on-line copy of this technical report is available.

- Some Connections Between the Minimal Polynomial and the Automorphism, November 1977 A. Mowshowitz, G. Criscuolo, R. Tortora and Chung-Mo Kwok
The relationship between the spectrum and the automorphism group of a graph is
probed with the aid of the theory of finite group representations. Three
related topics are explored: l) graphs with non-derogatory adjacency matrix, 2)
point-symmetric graphs, and 3) an algorithm for constructing the automorphism
group of a prime, point-symmetric graph. First, we give an upper bound on the
order of the automorphism group of a graph with non-derogatory adjacency matrix;
and show, in a special case, that the degree of each irreducible factor of the
minimal polynomial has a natural interpretation in terms of the automorphism
group. Second, we prove that the degree of the minimal polynomial of a
point-symmetric graph is bounded above by the number of orbits of the
stabilizer of any given element. For point-symmetric graphs with a prime
number of points, we exhibit a formula linking the degree of the minimal
polynomial with the order of the group. Finally, we give a simple algorithm
for constructing the automorphism group of a point-symmetric graph
with a prime number of points.

If you have any questions or comments regarding this page please send mail to
help@cs.ubc.ca.