Paper detail

Distance partitions of extremal and largest known circulant graphs of degree 2 to 9

This paper considers the degree-diameter problem for extremal and largest known undirected circulant graphs of degree 2 to 9 of arbitrary diameter. As these graphs are vertex transitive it is possible to define their distance partition. The number of vertices in each level of the distance partition is shown to be related to an established upper bound for the order of Abelian Cayley graphs. Furthermore these graphs are all found to have odd girth which is maximal for their diameter. Therefore the type of each vertex in a level may be well-defined by the number of adjacent vertices in the preceding level. With this definition the number of vertices of each type in each level is also shown to be related to the same Abelian Cayley graph upper bound. Finally some implications are discussed for circulant graphs of higher degree.