Some Connections Between the Minimal Polynomial and the Automorphism of a Graph

ID
TR-77-18
Authors
A. Mowshowitz, G. Criscuolo, R. Tortora, Chung-Mo Kwok
Publishing date
November 1977
Abstract

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: 1) 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.