Robert Lewis
Published 2014-04-11, updated 2014-08-05Version 3
This paper considers the degree-diameter problem for undirected circulant graphs. The focus is on extremal graphs of given (small) degree and arbitrary diameter. The published literature only covers graphs of up to degree 7. The approach used to establish the results for degree 6 and 7 has been extended successfully to degree 8 and 9. Candidate graphs are defined as functions of the diameter for both degree 8 and degree 9. They are proven to be extremal for small diameters. They establish new lower bounds for all greater diameters, and are conjectured to be extremal. The existence of the degree 8 solution is proved for all diameters. Finally some conjectures are made about solutions for circulant graphs of higher degree.
Comments: In order to avoid this paper being excessively long only an abridged version of the proof of Theorem 3 is included. The complete version is available as arXiv:1404.3949 for those interested in reading the details of all the steps
Extremal Graphs Without 4-Cycles
Extremal graphs for clique-paths
A proof of the stability of extremal graphs, Simonovits' stability from Szemerédi's regularity
![QR code for arXiv:1404.3948 [math.CO]](http://oss.arxitics.com/images/favicon.svg)