This site is supported by donations to The OEIS Foundation.



(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A049287 Number of nonisomorphic circulant graphs, i.e., undirected Cayley graphs for the cyclic group of order n. 12


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

%T 1312,423,1400,928,3104,1182,8768,2192,8364,6768,16460,11144,46784,

%U 14602,58288,44424,136128,52488,355200,99880,432576,351424,762608,364724,2122944,798952,3356408

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

%C Further values for (twice) squarefree and (twice) prime-squared orders can be found in the Liskovets reference.

%C Terms may be computed by filtering potentially isomorphic graphs of A285620 through nauty. - _Andrew Howroyd_, Apr 29 2017

%H Andrew Howroyd, <a href="/A049287/b049287.txt">Table of n, a(n) for n = 1..70</a>

%H V. Gatt, <a href="https://arxiv.org/abs/1703.06038">On the Enumeration of Circulant Graphs of Prime-Power Order: the case of p^3</a>, arXiv:1703.06038 [math.CO], 2017.

%H V. A. Liskovets, <a href="https://arxiv.org/abs/math/0104131">Some identities for enumerators of circulant graphs</a>, arXiv:math/0104131 [math.CO], 2001, <a href="http://dx.doi.org/10.1023/B:JACO.0000011937.70237.0b">J. Alg. Comb. 18 (2003) 189</a>

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

%H Brendan McKay, <a href="http://users.cecs.anu.edu.au/~bdm/nauty/">Nauty home page</a>.

%H R. Poeschel, <a href="http://www.math.tu-dresden.de/~poeschel/Publikationen.html">Publications</a>

%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/CirculantGraph.html">Circulant Graph</a>

%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/CirculantMatrix.html">Circulant Matrix</a>

%F There is an easy formula for prime orders. Formulae are also known for squarefree and prime-squared orders.

%F From _Andrew Howroyd_, Apr 24 2017: (Start)

%F a(n) <= A285620(n).

%F a(n) = A285620(n) for n squarefree or twice square free.

%F a(A000040(n)^2) = A038781(n).

%F a(n) = Sum_{d|n} A075545(d).

%F (End)

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

%Y Cf. A049297, A049288, A049289, A060966, A285620, A038781, A075545.

%K nonn,nice

%O 1,2

%A _Valery A. Liskovets_

%E a(48)-a(50) from _Andrew Howroyd_, Apr 29 2017

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 August 20 18:56 EDT 2019. Contains 326154 sequences. (Running on oeis4.)