

A049287


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


12



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
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

1,2


COMMENTS

Further values for (twice) squarefree and (twice) primesquared 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 PrimePower 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 primepower 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


FORMULA

There is an easy formula for prime orders. Formulae are also known for squarefree and primesquared 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_{dn} A075545(d).
(End)


MATHEMATICA

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


CROSSREFS

Cf. A049297, A049288, A049289, A060966, A285620, A038781, A075545.
Sequence in context: A334878 A285330 A048676 * A285620 A185959 A006799
Adjacent sequences: A049284 A049285 A049286 * A049288 A049289 A049290


KEYWORD

nonn,nice


AUTHOR

Valery A. Liskovets


EXTENSIONS

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


STATUS

approved



