Back to search

University of British Columbia

Use of the spectrum in graph isomorphism

Abstract

dc:description

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.

Degree

thesis:*
Name thesis:degree_name
Master of Science - MSc
Level thesis:degree_level
master's
Discipline thesis:degree_discipline
Computer Science
Grantor dc:publisher
University of British Columbia
Year dc:date
1976

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Gelbart, Rachel

Rights

dc:rights
Statement dc:rights
  • 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.
Language dc:language
eng

Identifiers

dc:identifier.*
Handle dc:identifier
http://hdl.handle.net/2429/20065

Chain of custody

source
Harvested from
University of British Columbia
Base URL
circle.library.ubc.ca/oai/request
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
related terms
citation

Gelbart, Rachel. Use of the spectrum in graph isomorphism. master's thesis, University of British Columbia, 1976. http://hdl.handle.net/2429/20065