Technical Reports

The ICICS/CS Reading Room


UBC CS TR-77-18 Summary

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.