login
This site is supported by donations to The OEIS Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A285620 Number of circulant graphs on n vertices up to Cayley isomorphism. 3
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 (list; graph; refs; listen; history; text; internal format)
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

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified July 17 20:45 EDT 2019. Contains 325109 sequences. (Running on oeis4.)