A049287 Number of nonisomorphic circulant graphs, i.e., undirected Cayley graphs for the cyclic group of order n.

1, 2, 2, 4, 3, 8, 4, 12, 8, 20, 8, 48, 14, 48, 44, 84, 36, 192, 60, 336, 200, 416, 188, 1312, 423, 1400, 928, 3104, 1182, 8768, 2192, 8364, 6768, 16460, 11144, 46784, 14602, 58288, 44424, 136128, 52488, 355200, 99880, 432576, 351424, 762608, 364724, 2122944, 798952, 3356408

Offset: 1

Author

Valery A. Liskovets

Keywords

• nonn
• nice

Comments

Further values for (twice) squarefree and (twice) prime-squared orders can be found in the Liskovets reference.

Terms may be computed by filtering potentially isomorphic graphs of A285620 through nauty. - Andrew Howroyd, Apr 29 2017

Links

• Andrew Howroyd, Table of n, a(n) for n = 1..70
• V. Gatt, On the Enumeration of Circulant Graphs of Prime-Power Order: the case of p^3, arXiv:1703.06038 [math.CO], 2017.
• V. A. Liskovets, Some identities for enumerators of circulant graphs, arXiv:math/0104131 [math.CO], 2001; J. Alg. Comb. 18 (2003) 189.
• V. A. Liskovets and R. Poeschel, On the enumeration of circulant graphs of prime-power and squarefree orders.
• Brendan McKay, Nauty home page.
• R. Poeschel, Publications.
• Eric Weisstein's World of Mathematics, Circulant Graph.
• Eric Weisstein's World of Mathematics, Circulant Matrix.

Crossrefs

Cf. A049297, A049288, A049289, A060966, A285620, A038781, A075545.

Programs

Mathematica

CountDistinct /@ Table[CanonicalGraph[CirculantGraph[n, #]] & /@ Subsets[Range[Floor[n/2]]], {n, 25}] (* Eric W. Weisstein, May 13 2017 *)

Formula

There is an easy formula for prime orders. Formulae are also known for squarefree and prime-squared orders.

From Andrew Howroyd, Apr 24 2017: (Start)

a(n) <= A285620(n).

a(n) = A285620(n) for n squarefree or twice square free.

a(A000040(n)^2) = A038781(n).

a(n) = Sum_{d|n} A075545(d).

(End)

Extensions

a(48)-a(50) from Andrew Howroyd, Apr 29 2017