Back to search

University of British Columbia

On the isomorphism problem for a class of bipartite graphs

Abstract

dc:description

The purpose of this thesis is to investigate the graph isomorphism problem for a special class of graphs. Each graph is characterized by its edge set, and a subgroup of its automorphism group, called the colour group. In particular, a simple, efficient algorithm for determining whether two graphs are isomorphic if at least one is a member of the class is developed. Chapter 1 provides some basic definitions and lemmas required in the text. The concepts of reducibility and reducible bipartite graphs are introduced, and the properties of the colour groups of such graphs are investigated. Chapter 2 establishes some results concerning the existence of reducible graphs. Conditions based on the existence of vertices with prescribed properties are shown to provide sufficient conditions for a graph to be reducible. In the special case of trees they are shown to be both necessary and sufficient. Necessary conditions for the reducibility of graphs, based on their radius and diameter are also established. Chapter 3 describes an algorithm for determining whether a graph is completely reducible, which is applied to a test for isomorphism. An investigation of the speed of this algorithm is made and its efficiency is compared with an algorithm of D. Corneil [5], which this author considers the best for arbitrary graphs in the current literature.

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
1970

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Dixon, Anthony H.

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/34625

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

Dixon, Anthony H.. On the isomorphism problem for a class of bipartite graphs. master's thesis, University of British Columbia, 1970. http://hdl.handle.net/2429/34625