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

Author

Andrew Howroyd, Apr 22 2017

Keywords

• nonn

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.

Crossrefs

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

Programs

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 *)

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));