Afzaly, Seyedeh Narjess

### Description

In this thesis, efficient isomorph-free generation of graph classes with the method of
generation by canonical construction path(GCCP) is discussed. The method GCCP
has been invented by McKay in the 1980s. It is a general method to recursively generate
combinatorial objects avoiding isomorphic copies. In the introduction chapter, the
method of GCCP is discussed and is compared to other well-known methods of generation.
The generation of the class of quartic graphs is used as an example to...[Show more] explain
this method. Quartic graphs are simple regular graphs of degree four. The programs,
we developed based on GCCP, generate quartic graphs with 18 vertices more than two
times as efficiently as the well-known software GENREG does.
This thesis also demonstrates how the class of principal graph pairs can be generated
exhaustively in an efficient way using the method of GCCP. The definition and
importance of principal graph pairs come from the theory of subfactors where each
subfactor can be modelled as a principal graph pair. The theory of subfactors has
applications in the theory of von Neumann algebras, operator algebras, quantum algebras
and Knot theory as well as in design of quantum computers. While it was
initially expected that the classification at index 3 + √5 would be very complicated,
using GCCP to exhaustively generate principal graph pairs was critical in completing
the classification of small index subfactors to index 5¼.
The other set of classes of graphs considered in this thesis contains graphs without
a given set of cycles. For a given set of graphs, H, the Turán Number of H, ex(n,H),
is defined to be the maximum number of edges in a graph on n vertices without a
subgraph isomorphic to any graph in H. Denote by EX(n,H), the set of all extremal
graphs with respect to n and H, i.e., graphs with n vertices, ex(n,H) edges and no
subgraph isomorphic to any graph in H. We consider this problem when H is a set of
cycles. New results for ex(n, C) and EX(n, C) are introduced using a set of algorithms
based on the method of GCCP. Let K be an arbitrary subset of {C3, C4, C5, . . . , C32}.
For given n and a set of cycles, C, these algorithms can be used to calculate ex(n, C)
and extremal graphs in Ex(n, C) by recursively extending smaller graphs without any
cycle in C where C = K or C = {C3, C5, C7, . . .} ᴜ K and n≤64. These results are
considerably in excess of the previous results of the many researchers who worked on
similar problems. In the last chapter, a new class of canonical relabellings for graphs, hierarchical
canonical labelling, is introduced in which if the vertices of a graph, G, is canonically
labelled by {1, . . . , n}, then G\{n} is also canonically labelled. An efficient hierarchical
canonical labelling is presented and the application of this labelling in generation
of combinatorial objects is discussed.

Items in Open Research are protected by copyright, with all rights reserved, unless otherwise indicated.