A285620 -id:A285620 - cp's OEIS frontend

A056391 Number of step shifted (decimated) sequence structures using a maximum of two different symbols.

1, 2, 3, 6, 6, 20, 14, 48, 52, 140, 108, 624, 352, 1400, 2172, 4464, 4116, 22112, 14602, 68016, 88376, 209936, 190746, 1075200, 839128, 2797000, 3730584, 11276704, 9587580, 67195520, 35792568

Offset: 1

Marks R. Nester

nonn

See A056371 for an explanation of step shifts. Permuting the symbols will not change the structure.

Also, number of circulant digraphs on n vertices up to Cayley isomorphism. 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 A049297). - Andrew Howroyd, Apr 20 2017

M. R. Nester (1999). Mathematical investigations of some plant interaction designs. PhD Thesis. University of Queensland, Brisbane, Australia.

G. C. Greubel, Table of n, a(n) for n = 1..1000 (terms 1..200 from Andrew Howroyd)
Andrew Howroyd, Polya Enumeration in PARI (many sequences included)
Marks R. Nester, Mathematical investigations of some plant interaction designs, Chapter 2, Finite and Periodic Sequences, plus Notes and Errata.

Row 2 of A285522.

Cf. A056371, A049297, A285620, A049287, A288620.

a[m_, n_] := (1/EulerPhi[n])*Sum[If[GCD[k, n] == 1, m^DivisorSum[n, EulerPhi[#]/MultiplicativeOrder[k, #]&], 0], {k, 1, n}]; a[n_] := a[2, n]/2; Array[a, 40] (* Jean-François Alcover, Jun 12 2017 *)

a(n)=sum(k=1, n, if(gcd(k, n)==1, 2^(sumdiv(n, d, eulerphi(d)/znorder(Mod(k, d)))-1), 0))/eulerphi(n); \\ Andrew Howroyd, Apr 20 2017

\\ alternative using Polya enumeration functions (see attachment)
a(n) = NonequivalentStructs(StepShiftPerms(n),2); \\ Andrew Howroyd, Oct 01 2017

Use de Bruijn's generalization of Polya's enumeration theorem as discussed in reference.
a(n) = A056371(n) / 2. - Andrew Howroyd, Apr 20 2017
a(n) = A288620(n, 2) + 1. - Andrew Howroyd, Jun 13 2017

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

Original entry on oeis.org

1, 2, 2, 4, 3, 8, 4, 12, 8, 20, 8, 48, 14, 48, 44, 84, 36, 192, 60, 336, 200, 416, 188, 1312, 423, 1400, 928, 3104, 1182, 8768, 2192, 8364, 6768, 16460, 11144, 46784, 14602, 58288, 44424, 136128, 52488, 355200, 99880, 432576, 351424, 762608, 364724, 2122944, 798952, 3356408

Offset: 1

Valery A. Liskovets

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

Terms may be computed by filtering potentially isomorphic graphs of A285620 through nauty. - Andrew Howroyd, Apr 29 2017

Andrew Howroyd, Table of n, a(n) for n = 1..70
V. Gatt, On the Enumeration of Circulant Graphs of Prime-Power Order: the case of p^3, arXiv:1703.06038 [math.CO], 2017.
V. A. Liskovets, Some identities for enumerators of circulant graphs, arXiv:math/0104131 [math.CO], 2001; J. Alg. Comb. 18 (2003) 189.
V. A. Liskovets and R. Poeschel, On the enumeration of circulant graphs of prime-power and squarefree orders.
Brendan McKay, Nauty home page.
R. Poeschel, Publications.
Eric Weisstein's World of Mathematics, Circulant Graph.
Eric Weisstein's World of Mathematics, Circulant Matrix.

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

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

There is an easy formula for prime orders. Formulae are also known for squarefree and prime-squared orders.
From Andrew Howroyd, Apr 24 2017: (Start)
a(n) <= A285620(n).
a(n) = A285620(n) for n squarefree or twice square free.
a(A000040(n)^2) = A038781(n).
a(n) = Sum_{d|n} A075545(d).
(End)

a(48)-a(50) from Andrew Howroyd, Apr 29 2017

A367554 a(n) is the number of 2n-regular circulant graphs of order 53.

Original entry on oeis.org

1, 1, 13, 100, 578, 2530, 8866, 25300, 60115, 120175, 204347, 297160, 371516, 400024, 371516, 297160, 204347, 120175, 60115, 25300, 8866, 2530, 578, 100, 13, 1, 1

Offset: 0

Andrey Zabolotskiy, Nov 22 2023

Brian Alspach and Marni Mishna, Enumeration of Cayley graphs and digraphs, Discr. Math., 256 (2002), 527-539.
Marni Mishna, Home page.
Marni Mishna, Publications.
Marni Mishna, Cayley Graph Enumeration, Master's Thesis, Simon Fraser University, 2000. See p. 16 (which is p. 24 in the pdf).

Cf. A000031, A049287, A285620.

from math import gcd, comb
from sympy import totient, divisors
def A367554(n): return sum(totient(d)*comb(26//d,n//d) for d in divisors(gcd(n,26),generator=True))//26 # Chai Wah Wu, Nov 23 2023

def a(k, p):
    return (2/(p-1)) * sum(euler_phi(d) * binomial((p-1)/(2*d), k/(2*d)) for d in divisors(gcd(k, p-1)/2)) # see Mishna; beware the missing prefactor (2/(p-1))
print([a(2*n, 53) for n in range(27)]) # Andrey Zabolotskiy, Nov 22 2023

Sum_n a(n) = 2581428 = A049287(53) = A285620(53) = A000031((53-1)/2). - Andrey Zabolotskiy, Nov 22 2023

A344517 Minimum diameter of 4-regular circulant graphs of order n.

Original entry on oeis.org

1, 1, 2, 2, 2, 2, 2, 2, 2, 2, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 7, 7, 7, 7, 7

Offset: 4

Andres Cicuttin, May 21 2021

nonn

F. Boesch and Jhing-Fa Wang, Reliable circulant networks with minimum transmission delay, IEEE Transactions on Circuits and Systems, vol. 32, no. 12, pp. 1286-1291, December 1985, doi: 10.1109/TCS.1985.1085667.
Bevan, David et al. Large circulant graphs of fixed diameter and arbitrary degree. Ars Math. Contemp. 13 (2017): 275-291.

R. Feria-Puron, H. Perez-Roses, and J. Ryan, Searching for Large Circulant Graphs, arXiv:1503.07357 [math.CO], 2015.
Eric Weisstein's World of Mathematics, Graph Diameter
Wikipedia, Circulant Graph

Cf. A049287, A075545, A285620.

mindiameter[n_]:=Module[{nmax,tab,stab},
nmax=Floor[n/2];
tab=Flatten[#,1]&@Table[Table[{n,i,j,GraphDiameter[CirculantGraph[n,{i,j}]]},{i,1,j-1}],{j,2,nmax}];
stab=Sort[tab,#1[[4]]<#2[[4]]&];
stab[[1]][[4]]//Return]
Table[mindiameter[n],{n,4,120}]
Table[Ceiling[(Sqrt[2n-1]-1)/2],{n,4,88}] (* Stefano Spezia, May 23 2021 *)

a(n) = ceiling((sqrt(2n-1)-1)/2).

cp's OEIS Frontend

A056391 Number of step shifted (decimated) sequence structures using a maximum of two different symbols.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Mathematica

PARI

PARI

Formula

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

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

Formula

Extensions

A367554 a(n) is the number of 2n-regular circulant graphs of order 53.

Views

Author

Keywords

Links

Crossrefs

Programs

Python

SageMath

Formula

A344517 Minimum diameter of 4-regular circulant graphs of order n.

Views

Author

Keywords

References

Links

Crossrefs

Programs

Mathematica

Formula