- Library Home /
- Search Collections /
- Open Collections /
- Browse Collections /
- UBC Theses and Dissertations /
- Use of the spectrum in graph isomorphism
Open Collections
UBC Theses and Dissertations
UBC Theses and Dissertations
Use of the spectrum in graph isomorphism Gelbart, Rachel
Abstract
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.
Item Metadata
Title |
Use of the spectrum in graph isomorphism
|
Creator | |
Publisher |
University of British Columbia
|
Date Issued |
1976
|
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.
|
Genre | |
Type | |
Language |
eng
|
Date Available |
2010-02-11
|
Provider |
Vancouver : University of British Columbia Library
|
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.
|
DOI |
10.14288/1.0051789
|
URI | |
Degree | |
Program | |
Affiliation | |
Degree Grantor |
University of British Columbia
|
Campus | |
Scholarly Level |
Graduate
|
Aggregated Source Repository |
DSpace
|
Item Media
Item Citations and Data
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.