The Degree Diameter Problem for Circulant Graphs

Table of the orders of the largest known circulant graphs

[math]d[/math]\[math]k[/math]	2	3	4	5	6	7	8	9	10
3	8	12	16	20	24	28	32	36	40
4	13	25	41	61	85	113	145	181	221
5	16	36	64	100	144	196	256	324	400
6	21	55	117	203	333	515	737	1 027	1 393
7	26	76	160	308	536	828	1 232	1 764	2 392
8	35	104	248	528	984	1 712	2 768	4 280	6 320
9	42	130	320	700	1 416	2 548	4 304	6 804	10 320
10	51	177	457	1 099	2 380	4 551	8 288	14 099	22 805
11	56	210	576	1 428	3 200	6 652	12 416	21 572	35 880
12	67	275	819	2 040	4 283	8 828	16 439	29 308	51 154
13	80	312	970	2 548	5 598	12 176	22 198	40 720	72 608
14	90	381	1 229	3 244	7 815	17 389	35 929	71 748	126 109
15	96	448	1 420	3 980	9 860	22 584	48 408	93 804	177 302
16	112	518	1 717	5 024	13 380	32 731	71 731	148 385	298 105

The following table is the key to the colors in the table presented above:

Color	Details
*	Numbers in bold indicate graphs known to be optimal.
*	Optimal graphs.
*	Optimal graphs found by E. Monakhova.
*	Graphs found by H. Macbeth, J. Šiagiová, J. Širáň and T. Vetrík.
*	Graphs found by R. Dougherty and V. Faber and independently for d=6 by E. Monakhova.
*	Graphs found by B. McKay.
*	Graphs found by R. Lewis.
*	Graphs found by R. Lewis and independently by R. Feria-Puron, H. Pérez-Rosés and J. Ryan.
*	Graphs found by R. Feria-Puron, H. Pérez-Rosés and J. Ryan.
*	Graphs found by D. Bevan, G. Erskine and R. Lewis.
*	Graphs found by O. Monakhov and E. Monakhova.

Table of the lowest upper bounds known at present, and the percentage of the order of the largest known graphs

[math]d[/math]\[math]k[/math]	2	3	4	5	6	7	8	9	10
3	8 100%	12 100%	16 100%	20 100%	24 100%	28 100%	32 100%	36 100%	40 100%
4	13 100%	25 100%	41 100%	61 100%	85 100%	113 100%	145 100%	181 100%	221 100%
5	16 100%	36 100%	64 100%	100 100%	144 100%	196 100%	256 100%	324 100%	400 100%
6	21 100%	55 100%	117 100%	203 100%	333 100%	515 100%	737 100%	1 027 100%	1 393 100%
7	26 100%	76 100%	160 100%	308 100%	536 100%	828 100%	1 232 100%	1 764 100%	2 392 100%
8	35 100%	104 100%	248 100%	528 100%	984 100%	1 712 100%	3 649 76%	5 641 76%	8 361 76%
9	42 100%	130 100%	320 100%	700 100%	1 416 100%	3 530 72%	5 890 73%	9 290 73%	14 002 74%
10	51 100%	177 100%	681 67%	1 683 65%	3 653 65%	7 183 63%	13 073 63%	22 363 63%	36 365 63%
11	56 100%	210 100%	912 63%	2 364 60%	5 336 60%	10 836 61%	20 256 61%	35 436 61%	58 728 61%
12	67 100%	275 100%	1 289 64%	3 653 56%	3 910 48%	19 825 45%	40 081 41%	75 517 39%	134 245 38%
13	80 100%	312 100%	1 666 58%	4 942 52%	12 642 44%	28 814 42%	59 906 37%	115 598 35%	209 762 35%
14	90 100%	381 100%	2 241 55%	7 183 45%	19 825 39%	48 639 36%	108 545 33%	224 143 32%	433 905 29%
15	96 100%	448 100%	2 816 50%	9 424 42%	27 008 37%	68 464 33%	157 184 31%	332 688 28%	658 048 27%
16	112 100%	833 62%	1 520 47%	4 551 38%	40 081 33%	108545 30%	265 729 27%	598 417 25%	1 256 465 24%

References

• D. Bevan, G. Erskine, and R. Lewis. Large circulant graphs of fixed diameter and arbitrary degree. ArXiv
• R. Feria-Puron, J. Ryan, and H. Perez-Roses. Searching for Large Multi-Loop Networks. Electronic Notes in Discrete Mathematics, vol. 46 (2014), pp. 233-240. doi:10.1016/j.endm.2014.08.031. Link to journal
• R.R. Lewis. The Degree/Diameter Problem for Circulant Graphs of Degree 8 and 9. The Electronic Journal of Combinatorics, vol. 21(4) (2014), #P4.50. Link to journal
• E.A. Monakhova, Synthesis of optimal Diophantine structures, Comput. Syst. Novosibirsk , 80 (1979), p.18--35. (in Russian).
• E. Monakhova, Optimal Triple Loop Networks with Given Transmission Delay: Topological Design and Routing, Inter. Network Optimization Conference, (INOC'2003), Evry/Paris, France, (2003), p.410--415.
• E.A. Monakhova . On synthesis of multidimensional circulant graphs of diameter two, Bulletin of the Tomsk Polytechnic University. 323(2) (2013), p.25--28. (in Russian). Link to journal