TY - THES
AU - Gelbart, Rachel
PY - 1976
TI - Use of the spectrum in graph isomorphism
KW - Thesis/Dissertation
LA - eng
M3 - Text
AB - The following is a study of the use of the eigenvalues and eigenvectors of the adjacency matrices of graphs to determine graph isomorphism. Two randomly chosen graphs will in general have different eigenvalues, and comparing the eigenvalues provides a first filter when checking for isomorphism. If the graphs are cospectral, we propose an algorithm that compares their eigenvectors in order to find an isomorphism between them, if any exists. The algorithm involves backtracking, and it is therefore difficult to evaluate its performance. It was fast for all pairs of graphs we compared, except one. For graphs whose eigenvalues are all simple we present an efficient algorithm to generate the group of a graph.
N2 - The following is a study of the use of the eigenvalues and eigenvectors of the adjacency matrices of graphs to determine graph isomorphism. Two randomly chosen graphs will in general have different eigenvalues, and comparing the eigenvalues provides a first filter when checking for isomorphism. If the graphs are cospectral, we propose an algorithm that compares their eigenvectors in order to find an isomorphism between them, if any exists. The algorithm involves backtracking, and it is therefore difficult to evaluate its performance. It was fast for all pairs of graphs we compared, except one. For graphs whose eigenvalues are all simple we present an efficient algorithm to generate the group of a graph.
UR - https://open.library.ubc.ca/collections/831/items/1.0051789
ER - End of Reference