Searching for Large Circulant Graphs

We address the problem of constructing large undirected circulant networks with given degree and diameter. First we discuss the theoretical upper bounds and their asymptotics, and then we describe and implement a computer-based method to find large circulant graphs with given parameters. For several combinations of degree and diameter, our algorithm produces the largest known circulant graphs. We summarize our findings in a table, up to degree 15 and diameter 10, and we perform a statistical analysis of this table, which can be useful for evaluating the performance of our methods, as well as other constructions in the future.