Back to search

The Open University

Analysis And Construction Of Extremal Circulant And Other Abelian Cayley Graphs

Abstract

dc:description.abstract

This thesis concerns the analysis and construction of extremal circulant and other Abelian Cayley graphs. For the purpose of this thesis, extremal graphs are understood as graphs with largest possible order for given degree and diameter, and the search for them is called the degree-diameter problem. The emphasis is on circulant graphs and on families of graphs defined for infinite diameter classes for given fixed degrees. <br></br><br></br> Most studies in the degree-diameter problem have employed candidate algebraic structures to generate graphs that successively improve on previous best results. In contrast, this study has made extensive use of computer searches to find extremal graphs and graph families directly, and has then sought the algebra that describes them. In this way, the maximum degree for which largest-known circulant graph families have been discovered, with order greater than the legacy lower bound, has been increased from 7 to 20 and beyond. <br></br><br></br> Topics covered include graphs in the following categories, undirected unless stated otherwise: circulant, other Abelian Cayley, bipartite circulant, arc-transitive circulant, directed circulant and mixed circulant; and their main properties such as distance partition, odd girth and automorphism group size. <br></br><br></br> A major aspect of this thesis is the analysis of a matrix associated with each graph family, the <i>lattice generator matrix</i>, with newly discovered properties such as quasimaximality, radius maximality and eccentricity. Important new relationships between graph families of common dimension have also been discovered: translation, conjugation and transposition. <br></br><br></br> An Extremal Order Conjecture is established for extremal undirected circulant and other Abelian Cayley graphs of any degree and diameter. An equivalent conjecture for directed circulant graphs and certain classes of mixed circulants is also established. Most of the extremal and largest-known graphs and graph families presented here have been discovered by the author and are documented comprehensively in the appendices.

Degree

thesis:*
Name dc:type.qualificationname
phd
Level dc:type.qualificationlevel
doctoral
Grantor dc:publisher.institution
The Open University
Year dc:date.issued
2021

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Lewis, Robert Roderick

Rights

Language dc:language
en

Chain of custody

source
Harvested from
The Open University
Base URL
oro.open.ac.uk/cgi/oai2
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
related terms
citation

Lewis, Robert Roderick. Analysis And Construction Of Extremal Circulant And Other Abelian Cayley Graphs. doctoral thesis, The Open University, 2021.