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	11	12
3	8	12	16	20	24	28	32	36	40	44	48
4	13	25	41	61	85	113	145	181	221	265	313
5	16	36	64	100	144	196	256	324	400	484	576
6	21	55	117	203	333	515	737	1 027	1 393	1 815	2 329
7	26	76	160	308	536	828	1 232	1 764	2 392	3 180	4 144
8	35	104	248	528	984	1 712	2 768	4 280	6 320	9 048	12 552
9	42	130	320	700	1 416	2 548	4 304	6 804	10 320	15 004	21 192
10	51	177	457	1 099	2 380	4 551	8 288	14 099	22 805	35 568	53 025
11	56	210	576	1 428	3 200	6 652	12 416	21 572	35 880	56 700	87 248
12	67	275	819	2 120	5 044	10 777	21 384	39 996	69 965	117 712	190 392
13	80	312	970	2 676	6 256	14 740	30 760	57 396	106 120	182 980	295 840
14	90	381	1 229	3 695	9 800	23 304	49 757	103 380	196 689	350 700	593 989
15	96	448	1 420	4 292	12 232	32 092	68 944	142 516	276 928	514 580	908 480
16	112	518	1 788	5 847	17 733	44 328	107 748	232 245	479 255	924 420	1 702 428
17	130	570	1 954	6 468	20 360	57 684	136 512	321 780	659 464	1 350 820	2 479 104
18	138	655	2 645	8 248	27 273	78 513	205 601	483 523	1 061 864	2 202 955	4 388 640
19	156	722	2 696	9 652	30 864	99 420	257 144	652 004	1 388 608	3 101 860	6 100 520
20	171	815	3 175	12 396	39 733	132 720	358 089	930 184	2 232 648	4 529 265	10 121 820

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 G. Erskine.
*	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	11	12
3	8 100%	12 100%	16 100%	20 100%	24 100%	28 100%	32 100%	36 100%	44 100%	48 100%	40 100%
4	13 100%	25 100%	41 100%	61 100%	85 100%	113 100%	145 100%	181 100%	221 100%	265 100%	313 100%
5	16 100%	36 100%	64 100%	100 100%	144 100%	196 100%	256 100%	324 100%	400 100%	484 100%	576 100%
6	21 100%	55 100%	117 100%	203 100%	333 100%	515 100%	737 100%	1 027 100%	1 393 100%	1 815 100%	2 329 100%
7	26 100%	76 100%	160 100%	308 100%	536 100%	828 100%	1 232 100%	1 764 100%	2 392 100%	3 608 88%	4 672 89%
8	35 100%	104 100%	248 100%	528 100%	984 100%	1 712 100%	3 649 76%	5 641 76%	8 361 76%	11 969 76%	16 641 75%
9	42 100%	130 100%	320 100%	700 100%	1 416 100%	3 530 72%	5 890 73%	9 290 73%	14 002 74%	20 330 74%	28 610 74%
10	51 100%	177 100%	457 100%	1 099 100%	3 653 65%	7 183 63%	13 073 63%	22 363 63%	36 365 63%	56 695 63%	85 305 62%
11	56 100%	210 100%	576 100%	2 364 60%	5 336 60%	10 836 61%	20 256 61%	35 436 61%	58 728 61%	93 060 61%	142 000 61%
12	67 100%	275 100%	1 289 64%	3 653 58%	8 989 56%	19 825 54%	40 081 53%	75 517 53%	134 245 52%	227 305 52%	369 305 52%
13	80 100%	312 100%	1 666 58%	4 942 54%	12 642 49%	28 814 51%	59 906 51%	115 598 50%	209 762 51%	361 550 51%	596610 50%
14	90 100%	381 100%	2 241 55%	7 183 51%	19 825 49%	48 639 48%	108 545 46%	224 143 46%	433 905 45%	795 455 44%	1 392 065 43%
15	96 100%	448 100%	2 816 50%	9 424 46%	27 008 45%	68 464 47%	157 184 44%	332 688 43%	658 048 42%	1 229 360 42%	2 187 520 42%
16	112 100%	833 62%	3 649 49%	13 073 45%	40 081 44%	108 545 41%	265 729 41%	598 417 39%	1 256 465 38%	2 485 825 37%	4 673 345 36%
17	130 100%	978 58%	4 482 44%	16 722 39%	53 154 38%	148 626 39%	374 274 36%	864 146 37%	1 854 882 36%	3 742 290 36%	7 159 170 35%
18	138 100%	1 159 57%	5 641 47%	22 363 37%	75 517 36%	224 143 35%	598 417 34%	1 462 563 33%	3 317 445 31%	7 059 735 31%	14 218 905 31%
19	156 100%	1 340 54%	6 800 40%	28 004 34%	97 880 32%	299 660 33%	822 560 31%	2 060 980 32%	4 780 008 29%	10 377 180 30%	21 278 640 29%
20	171 100%	1 561 52%	8 361 38%	36 365 34%	134 245 30%	433 905 31%	1 256 465 28%	3 317 445 28%	8 097 453 28%	18 474 633 25%	39 753 273 25%

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