Open Collections

On the isomorphism problem for a class of bipartite graphs

University of British Columbia

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.

Text

2011-05-17

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.

http://hdl.handle.net/2429/34625

Computer Science

University of British Columbia

Graduate