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

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

Author

Andres Cicuttin, May 21 2021

Keywords

• nonn

References

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

Links

• 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

Crossrefs

Cf. A049287, A075545, A285620.

Programs

Mathematica

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

Formula

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