A285620 Number of circulant graphs on n vertices up to Cayley isomorphism.

1, 2, 2, 4, 3, 8, 4, 12, 8, 20, 8, 48, 14, 48, 44, 88, 36, 192, 60, 336, 200, 416, 188, 1344, 424, 1400, 944, 3104, 1182, 8768, 2192, 8784, 6768, 16460, 11144, 46848, 14602, 58288, 44424, 138432, 52488, 355200, 99880, 432576, 351712, 762608, 364724, 2151936, 798960

Offset

1,2

Comments

Two circulant graphs are Cayley isomorphic if there is a d, which is necessarily prime to n, that transforms through multiplication modulo n the step values of one graph into those of the other. For squarefree n this is the only way that two circulant graphs can be isomorphic (See A049287).

Links

Andrew Howroyd, Table of n, a(n) for n = 1..200

V. A. Liskovets and R. Poeschel, On the enumeration of circulant graphs of prime-power and squarefree orders.

Mathematica

IsLeastPoint[s_, f_] := Module[{t = f[s]}, While[t > s, t=f[t]]; Boole[s == t]];
c[n_, k_] := Sum[IsLeastPoint[u, Abs[Mod[#*k + Quotient[n, 2], n] - Quotient[n, 2]]&], {u, 1, n/2}];
a[n_] := If[n < 3, n, Sum[If[GCD[k, n] == 1, 2^c[n, k], 0]*2/EulerPhi[n], {k, 1, n/2}]];
Array[a, 50] (* Jean-François Alcover, Jun 12 2017, translated from PARI *)

Prog

(PARI)
IsLeastPoint(s, f)={my(t=f(s)); while(t>s, t=f(t)); s==t}
C(n, k)=sum(u=1, n/2, IsLeastPoint(u, v->abs((v*k+n\2)%n-n\2)));
a(n)=if(n<3, n, sum(k=1, n/2, if (gcd(k, n)==1, 2^C(n, k), 0))*2/eulerphi(n));

Crossrefs

Cf. A049287, A056391 (circulant digraphs), A049297, A038782.

Sequence in context: A285330 A048676 A049287 * A185959 A006799 A056429

Adjacent sequences: A285617 A285618 A285619 * A285621 A285622 A285623

Keyword

nonn

Author

Andrew Howroyd, Apr 22 2017

Status

approved