2018/03/18 by Robert R. Lewis, Lewis, Robert R
Computer Science · Mathematics · #05C35 #Combinatorics (math.CO) #FOS: Mathematics #Finite Group Theory Research #Graph theory and applications #Interconnection Networks and Systems
paper · pdf · doi:10.48550/arxiv.1803.07071
openalex publication_date 2018/03/18 · openalex created_date 2022/09/14 · openalex updated_date 2026/07/28
This paper considers the degree-diameter problem for undirected circulant\ngraphs. For degrees 10 and 11 newly discovered families of circulant graphs of\narbitrary diameter are presented which are largest known and are conjectured to\nbe extremal. They are also the largest-known Abelian Cayley graphs of these\ndegrees. For each such family the order of every graph in the family is defined\nby a quintic polynomial function of the diameter which is specific to the\nfamily. The elements of the generating set for each graph are similarly defined\nby a set of polynomials in the diameter. The existence of the graphs in the\ndegree 10 families has been proved for all diameters. These graphs are\nconsistent with a conjecture on the order of extremal Abelian Cayley and\ncirculant graphs of any degree and diameter.\n This is the extended version of the paper, including the proof steps for\ndegree 10 graphs covering all diameter classes and an appendix listing\nadditional tables of generating sets.\n