A389627 Triangle read by rows: T(n,k) is the number of circulant graphs with n vertices and degree k, (0 <= k < n).

1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 0, 1, 0, 1, 1, 1, 2, 2, 1, 1, 1, 0, 1, 0, 1, 0, 1, 1, 1, 2, 2, 2, 2, 1, 1, 1, 0, 2, 0, 2, 0, 2, 0, 1, 1, 1, 2, 2, 4, 4, 2, 2, 1, 1, 1, 0, 1, 0, 2, 0, 2, 0, 1, 0, 1, 1, 1, 4, 4, 7, 7, 7, 7, 4, 4, 1, 1, 1, 0, 1, 0, 3, 0, 4, 0, 3, 0, 1, 0, 1

Offset

1,18

Comments

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

All circulant graphs are vertex-transitive, so the table in A319367 provides an upper bound for this sequence. When n (the order) is prime, it is an equality. The smallest value for which they differ is T(8,3), due to the cube.

In the links, Turner has rows for n = 3, 5, 7, 11, 13, 17, 19. Liskovets has n = 7, 13, 14, 19, 37, 38, 61, 62, 73, 74. Gatt has n = 27 and 125, and Mishna has n = 53.

Links

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

Victoria Gatt, On the Enumeration of Circulant Graphs of Prime-Power Order: the case of p^3, arXiv:1703.06038 [math.CO], 2017.

Valery A. Liskovets, Some identities for enumerators of circulant graphs, arXiv:math/0104131 [math.CO], 2001; J. Alg. Comb. 18 (2003) 189.

Brendan McKay, Graphs page.

Marni Mishna, Cayley Graph Enumeration, Master's Thesis, Simon Fraser University, 2000.

James Turner, Point-symmetric graphs with a prime number of points, J. Comb. Theory 3, 136-145 (1967).

Eric Weisstein's World of Mathematics, Circulant Graph.

Formula

T(n,k) <= A319367(n,k).

T(p,k) = A319367(p,k) for p prime.

T(n,k) = T(n,n-1-k).

T(n,k) = 0 for n, k both odd.

T(n,0) = 1 = T(n,n-1).

T(n,1) = 1 for n even.

T(n,k) = T(n,k+1) for n, k both even (add edges between antipodal vertices).

Example

Triangle begins, n >= 1, 0 <= k < n:
  1;
  1, 1;
  1, 0, 1;
  1, 1, 1, 1;
  1, 0, 1, 0,  1;
  1, 1, 2, 2,  1,  1;
  1, 0, 1, 0,  1,  0,  1;
  1, 1, 2, 2,  2,  2,  1,  1;
  1, 0, 2, 0,  2,  0,  2,  0,  1;
  1, 1, 2, 2,  4,  4,  2,  2,  1,  1;
  1, 0, 1, 0,  2,  0,  2,  0,  1,  0,  1;
  1, 1, 4, 4,  7,  7,  7,  7,  4,  4,  1,  1;
  1, 0, 1, 0,  3,  0,  4,  0,  3,  0,  1,  0,  1;
  1, 1, 2, 2,  5,  5,  8,  8,  5,  5,  2,  2,  1,  1;
  1, 0, 3, 0,  7,  0, 11,  0, 11,  0,  7,  0,  3,  0, 1;
  1, 1, 3, 3,  7,  7, 10, 10, 10, 10,  7,  7,  3,  3, 1, 1;
  1, 0, 1, 0,  4,  0,  7,  0, 10,  0,  7,  0,  4,  0, 1, 0, 1;
  1, 1, 4, 4, 10, 10, 20, 20, 26, 26, 20, 20, 10, 10, 4, 4, 1, 1;
  ...
Larger values can be obtained from the files on Brendan McKay's site.
The circulant graphs with n=5 are 5K_1, C_5, and K_5.
The circulant graphs with n=6 are 6K_1, 3K_2, C_6, 2K_3, K_3,3, K_3 X K_2, K_2,2,2, and K_6.

Crossrefs

Row sums are A049287.

Cf. A023645 (k=2 column).

Cf. A367554 (n=53 row).

Cf. A049287, A075545, A049289 (circulant graphs).

Cf. A319367 (vertex transitive graphs table).

Cf. A319372 (Cayley graphs table).

Sequence in context: A204433 A004578 A388724 * A319372 A319367 A378007

Adjacent sequences: A389624 A389625 A389626 * A389628 A389629 A389630

Keyword

nonn,tabl

Author

Allan Bickle, Oct 09 2025

Status

approved