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

%I #22 Aug 06 2024 06:32:51

%S 1,2,2,4,3,8,4,12,8,20,8,48,14,48,44,88,36,192,60,336,200,416,188,

%T 1344,424,1400,944,3104,1182,8768,2192,8784,6768,16460,11144,46848,

%U 14602,58288,44424,138432,52488,355200,99880,432576,351712,762608,364724,2151936,798960

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

%C 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).

%H Andrew Howroyd, <a href="/A285620/b285620.txt">Table of n, a(n) for n = 1..200</a>

%H V. A. Liskovets and R. Poeschel, <a href="https://citeseerx.ist.psu.edu/pdf/b76573e0c2df2ff117cef015809e232a3747f585">On the enumeration of circulant graphs of prime-power and squarefree orders.</a>

%t IsLeastPoint[s_, f_] := Module[{t = f[s]}, While[t > s, t=f[t]]; Boole[s == t]];

%t c[n_, k_] := Sum[IsLeastPoint[u, Abs[Mod[#*k + Quotient[n, 2], n] - Quotient[n, 2]]&], {u, 1, n/2}];

%t a[n_] := If[n < 3, n, Sum[If[GCD[k, n] == 1, 2^c[n, k], 0]*2/EulerPhi[n], {k, 1, n/2}]];

%t Array[a, 50] (* _Jean-François Alcover_, Jun 12 2017, translated from PARI *)

%o (PARI)

%o IsLeastPoint(s,f)={my(t=f(s)); while(t>s,t=f(t));s==t}

%o C(n,k)=sum(u=1,n/2,IsLeastPoint(u,v->abs((v*k+n\2)%n-n\2)));

%o a(n)=if(n<3, n, sum(k=1, n/2, if (gcd(k, n)==1, 2^C(n,k),0))*2/eulerphi(n));

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

%K nonn

%O 1,2

%A _Andrew Howroyd_, Apr 22 2017