A389815 Number of vertex-transitive graphs with n vertices that are not circulant.

0, 0, 0, 0, 0, 0, 0, 2, 1, 2, 0, 26, 0, 8, 4, 202, 0, 188, 0, 878, 40, 400, 0, 14194, 41, 2836, 506, 22746, 0, 37540, 0, 669038, 0, 116120, 6, 1916418, 0, 755928, 4038, 12968042, 0, 9107026, 0, 38702064, 47996, 33571192, 0

Offset

1,8

Comments

A graph is vertex-transitive if, given any two vertices u and v of G, there is an automorphism that maps u to v.

The circulant graph C_n (a_1,...,a_r) has vertices v_1,...,v_n and all edges v_i-v_j whenever |i-j| = a_k mod n. (It can be rotated onto itself.)

Every vertex-transitive graph is circulant, and these are equivalent when n is prime.

If a graph is vertex-transitive but not circulant, then its complement is also. Thus a(n) will be even unless n = 4k+1 and n is not prime.

Links

Table of n, a(n) for n=1..47.

Eric Weisstein's World of Mathematics, Circulant Graph.

Eric Weisstein's World of Mathematics, Vertex-Transitive Graph.

Formula

a(n) = A006799(n) - A049287(n).

a(p) = 0 for p prime.

Example

The smallest vertex-transitive graphs that are not circulant are the cube and its complement, so a(8) = 2.
The Paley graph with order 9 is the only example with 9 vertices, so a(9) = 1.
The Petersen graph and its complement are the only examples with 10 vertices, so a(10) = 2.
Any prism graph with n = 4k is vertex-transitive but not circulant, so a(4k) >= 2 for k>1.

Crossrefs

Cf. A006799 (vertex-transitive graphs), A049287 (circulant graphs).

Sequence in context: A379781 A356919 A278158 * A218880 A024356 A390514

Adjacent sequences: A389812 A389813 A389814 * A389816 A389817 A389818

Keyword

nonn

Author

Allan Bickle, Oct 15 2025

Status

approved