On the Analytic Enumeration of Circulant Graphs

Preprint series: TU Dresden, Technical Report MATH-AL-07-2003, (43 pages)

MSC 2000

05C30 Enumeration of graphs and maps

05C25 Graphs and groups

05C20 Directed graphs (digraphs), tournaments

Abstract
We systematize, extend, and survey results of the analytical (i.e. represented by formulae) exact enumeration of circulant graphs. A convenient unified approach to counting various types of circulant graphs possessing the so-called Cayley isomorphism (CI) property is proposed. The results are represented uniformly in terms of well-specified Abelian permutation groups and their cycle index polynomials. This technique comprises mostly square-free orders, but it may be generalized to prime-squared (and also prime-power) orders, due to an isomorphism criterion for circulants of these orders. In the last section we provide vast numerical tables and suggest two conjectures.

Keywords: circulant graph, Cayley isomorphism, cyclic group, multiplier, graph enumeration, P{\'o}lya's method