login
Minimum diameter of 4-regular circulant graphs of order n.
1

%I #20 Jun 13 2021 03:33:50

%S 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,

%T 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,

%U 6,6,6,6,6,6,6,6,6,6,6,6,6,6,7,7,7,7,7

%N Minimum diameter of 4-regular circulant graphs of order n.

%D 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.

%D Bevan, David et al. Large circulant graphs of fixed diameter and arbitrary degree. Ars Math. Contemp. 13 (2017): 275-291.

%H R. Feria-Puron, H. Perez-Roses, and J. Ryan, <a href="http://arxiv.org/abs/1503.07357">Searching for Large Circulant Graphs</a>, arXiv:1503.07357 [math.CO], 2015.

%H Eric Weisstein's World of Mathematics, <a href="https://mathworld.wolfram.com/GraphDiameter.html">Graph Diameter</a>

%H Wikipedia, <a href="https://en.wikipedia.org/wiki/Circulant_graph">Circulant Graph</a>

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

%t mindiameter[n_]:=Module[{nmax,tab,stab},

%t nmax=Floor[n/2];

%t tab=Flatten[#,1]&@Table[Table[{n,i,j,GraphDiameter[CirculantGraph[n,{i,j}]]},{i,1,j-1}],{j,2,nmax}];

%t stab=Sort[tab,#1[[4]]<#2[[4]]&];

%t stab[[1]][[4]]//Return]

%t Table[mindiameter[n],{n,4,120}]

%t Table[Ceiling[(Sqrt[2n-1]-1)/2],{n,4,88}] (* _Stefano Spezia_, May 23 2021 *)

%Y Cf. A049287, A075545, A285620.

%K nonn

%O 4,3

%A _Andres Cicuttin_, May 21 2021