A049297 Number of nonisomorphic circulant digraphs (i.e., Cayley digraphs for the cyclic group) of order n.

1, 2, 3, 6, 6, 20, 14, 46, 51, 140, 108, 624, 352, 1400, 2172, 4262, 4116, 22040, 14602, 68016, 88376, 209936, 190746, 1062592, 839094, 2797000, 3728891, 11276704, 9587580, 67195520, 35792568

Offset: 1

Author

Valery A. Liskovets

Keywords

• nonn
• nice

Comments

Terms may be computed by filtering potentially isomorphic graphs of A056391 through nauty. Terms computed in this way for a(25), a(27) agree with theoretical calculations by others. - Andrew Howroyd, Apr 23 2017

Links

• V. A. Liskovets, Some identities for enumerators of circulant graphs, arXiv:math/0104131 [math.CO], 2001.
• V. A. Liskovets and R. Poeschel, On the enumeration of circulant graphs of prime-power and squarefree orders.
• R. Poeschel, Publications.
• V. Gatt, On the Enumeration of Circulant Graphs of Prime-Power Order: the case of p^3, arXiv:1703.06038 [math.CO], 2017.
• Victoria Gatt, Mikhail Klin, Josef Lauri, Valery Liskovets, From Schur Rings to Constructive and Analytical Enumeration of Circulant Graphs with Prime-Cubed Number of Vertices, in Isomorphisms, Symmetry and Computations in Algebraic Graph Theory, (Pilsen, Czechia, WAGT 2016) Vol. 305, Springer, Cham, 37-65.
• Brendan McKay, Nauty home page.

Crossrefs

Cf. A049287-A049289, A056391, A038777.

Programs

GAP

LoadPackage("grape");
CirculantDigraphCount:= function(n) local g; # slow for n >= 10
g:=Graph( Group(()), [1..n], OnPoints, function(x,y) return (y-x) mod n = 1; end,false);
return Length(GraphIsomorphismClassRepresentatives(List(Combinations([1..n]), s->DistanceGraph(g,s))));
end; # Andrew Howroyd, Apr 23 2017

Formula

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

From Andrew Howroyd, Apr 23 2017: (Start)

a(n) <= A056391(n).

a(n) = A056391(n) for squarefree n.

a(A000040(n)^2) = A038777(n).

(End)

Extensions

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

a(14) corrected by Andrew Howroyd, Apr 23 2017

a(16)-a(31) from Andrew Howroyd, Apr 23 2017