The Open UniversitySkip to content

Diameter, Girth And Other Properties Of Highly Symmetric Graphs

Erskine, Grahame (2017). Diameter, Girth And Other Properties Of Highly Symmetric Graphs. PhD thesis The Open University.

Full text available as:
PDF (Version of Record) - Requires a PDF viewer such as GSview, Xpdf or Adobe Acrobat Reader
Download (885kB) | Preview
Google Scholar: Look up in Google Scholar


We consider a number of problems in graph theory, with the unifying theme being the properties of graphs which have a high degree of symmetry.

In the degree-diameter problem, we consider the question of finding asymptotically large graphs of given degree and diameter. We improve a number of the current best published results in the case of Cayley graphs of cyclic, dihedral and general groups.

In the degree-diameter problem for mixed graphs, we give a new corrected formula for the Moore bound and show non-existence of mixed Cayley graphs of diameter 2 attaining the Moore bound for a range of open cases.

In the degree-girth problem, we investigate the graphs of Lazebnik, Ustimenko and Woldar which are the best asymptotic family identified to date. We give new information on the automorphism groups of these graphs, and show that they are more highly symmetrical than has been known to date.

We study a related problem in group theory concerning product-free sets in groups, and in particular those groups whose maximal product-free subsets are complete. We take a large step towards a classification of such groups, and find an application to the degree-diameter problem which allows us to improve an asymptotic bound for diameter 2 Cayley graphs of elementary abelian groups.

Finally, we study the problem of graphs embedded on surfaces where the induced map is regular and has an automorphism group in a particular family. We give a complete enumeration of all such maps and study their properties.

Item Type: Thesis (PhD)
Copyright Holders: 2017 The Author
Keywords: graph theory; Cayley graphs; group theory; automorphisms; Abelian groups
Academic Unit/School: Faculty of Science, Technology, Engineering and Mathematics (STEM)
Faculty of Science, Technology, Engineering and Mathematics (STEM) > Mathematics and Statistics
Item ID: 49440
Depositing User: Grahame Erskine
Date Deposited: 07 Jun 2017 16:01
Last Modified: 02 May 2018 14:29
Share this page:

Download history for this item

These details should be considered as only a guide to the number of downloads performed manually. Algorithmic methods have been applied in an attempt to remove automated downloads from the displayed statistics but no guarantee can be made as to the accuracy of the figures.

Actions (login may be required)

Policies | Disclaimer

© The Open University   contact the OU