A075545 -id:A075545 - cp's OEIS frontend

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

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

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

A344574 Number of ordered pairs (i,j) with 0 < i < j < n such that gcd(i,j,n) > 1.

Original entry on oeis.org

0, 0, 0, 0, 0, 1, 0, 3, 1, 6, 0, 13, 0, 15, 7, 21, 0, 37, 0, 39, 16, 45, 0, 73, 6, 66, 28, 81, 0, 130, 0, 105, 46, 120, 21, 181, 0, 153, 67, 189, 0, 262, 0, 213, 118, 231, 0, 337, 15, 306, 121, 303, 0, 433, 51, 369, 154, 378, 0, 583, 0, 435, 217, 465

Offset: 1

Andres Cicuttin, May 23 2021

A 4-regular circulant graph of order n, C(n,i,j), is connected if and only if gcd(n,i,j) = 1, where 0 < i < j < n.

a(n) >= 1 iff n is a composite > 4. - Robert Israel, Nov 26 2024

			a(8) = 3 via (i, j, n) in {(2, 4, 8), (2, 6, 8), (4, 6, 8)} and that's three such tuples. - _David A. Corneth_, Nov 27 2024

Robert Israel, Table of n, a(n) for n = 1..10000
Paul Theo Meijer, Connectivities and diameters of circulant graphs, Thesis, 1991, Simon Fraser University.
Eric Weisstein's World of Mathematics, Circulant Graph

Cf. A000741, A075545, A344517.

f:= proc(n) local t,i,g;
t:= 0:
for i from 1 to n-2 do
  g:= igcd(i,n);
  if g > 1 then t:= t + nops(select(s -> igcd(s,g) > 1, [$i+1..n-1])) fi
od:
t;
end proc:
map(f, [$1..80]); # Robert Israel, Nov 26 2024

npairs[n_]:=Module[{k=0},
Do[Do[
If[GCD[i,j,n]>1,k++]
,{i,1,j-1}],{j,2,n-1}];
Return[k]];
Table[npairs[n],{n,1,60}]

a(n) = {my(res = 0, d = divisors(factorback(factor(n)[,1]))); for(i = 2, #d, res+= moebius(d[i])*binomial((n-1)\d[i], 2)); -res} \\ David A. Corneth, Nov 27 2024

cp's OEIS Frontend

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

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

Views

Author

Keywords

References

Links

Crossrefs

Programs

Mathematica

Formula

A344574 Number of ordered pairs (i,j) with 0 < i < j < n such that gcd(i,j,n) > 1.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

PARI