UBC Theses and Dissertations

UBC Theses Logo

UBC Theses and Dissertations

On the minimal polynomial and authomorpism group of a graph Ng, Fat-Kwong Louis


This thesis discusses the use of the characteristic polynomial and minimal polynomial of the adjacency matrix of a graph to characterize its automorphism group. We first consider the reducibility of the minimal polynomial of a graph and see how this reflects the properties of the graph and its automorphism group. Then we study the relationship between the number of orbits of a subgroup of the automorphism group of a graph and the factorization of its characteristic polynomial. Finally we present an algorithm to determine the automorphism partitioning of a graph using its characteristic polynomial. Most of the results can also be extended to directed graphs and to graphs with parallel edges and loops.

Item Media

Item Citations and Data


For non-commercial purposes only, such as research, private study and education. Additional conditions apply, see Terms of Use https://open.library.ubc.ca/terms_of_use.