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,3

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

Table of n, a(n) for n=4..90.

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

Formula

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

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

Crossrefs

Cf. A049287, A075545, A285620.

Sequence in context: A000193 A059939 A071842 * A371355 A085141 A082896

Adjacent sequences: A344514 A344515 A344516 * A344518 A344519 A344520

Keyword

nonn

Author

Andres Cicuttin, May 21 2021

Status

approved