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	13	14	15	16
3	8	12	16	20	24	28	32	36	40	44	48	52	56	60	64
4	13	25	41	61	85	113	145	181	221	265	313	365	421	481	545
5	16	36	64	100	144	196	256	324	400	484	576	676	784	900	1 024
6	21	55	117	203	333	515	737	1 027	1 393	1 815	2 329	2 943	3 629	4 431	5 357
7	26	76	160	308	536	828	1 232	1 764	2 392	3 180	4 144	5 236	6 536	8 060	9 744
8	35	104	248	528	984	1 712	2 768	4 280	6 320	9 048	12 552	17 024	22 568	29 408	37 664
9	42	130	320	700	1 416	2 548	4 304	6 804	10 320	15 004	21 192	29 068	39 032	51 300	66 336
10	51	177	457	1 099	2 380	4 551	8 288	14 099	22 805	35 568	53 025	77 572	110 045	152 671	208 052
11	56	210	576	1 428	3 200	6 652	12 416	21 572	35 880	56 700	87 248	128 852	184 424	259 260	355 576
12	67	275	819	2 120	5 044	10 777	21 384	39 996	69 965	117 712	190 392	295 840	448 920	662 680	952 985
13	80	312	970	2 676	6 256	14 740	30 760	57 396	106 120	182 980	295 840	476 100	732 744	1 081 860	1 593 064
14	90	381	1 229	3 695	9 800	23 304	49 757	103 380	196 689	350 700	593 989	996 240	1 603 216	2 486 227	3 843 540
15	96	448	1 420	4 292	12 232	32 092	68 944	142 516	276 928	514 580	908 480	1 550 228	2 566 712	4 013 468	6 155 056
16	112	518	1 788	5 847	17 733	44 328	107 748	232 245	479 255	924 420	1 702 428	2 982 623	5 209 347	8 476 048	13 588 848
17	130	570	1 954	6 468	20 360	57 684	136 512	321 780	659 464	1 350 820	2 479 104	4 557 364	7 729 000	13 275 108	21 252 864
18	138	655	2 645	8 248	27 273	80 940	205 601	483 523	1 078 280	2 202 955	4 388 640	8 068 383	14 718 984	25 609 955	43 068 508
19	156	722	2 696	9 652	30 864	99 420	257 144	652 004	1 388 608	3 101 860	6 100 520	11 797 684	21 659 528	38 156 524	66 601 304
20	171	815	3 175	12 396	39 733	132 720	358 089	930 184	2 232 648	4 529 265	10 121 820	19 505 285	38 155 632	70 612 644	119 170 289

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	13	14	15	16
3	8 100%	12 100%	16 100%	20 100%	24 100%	28 100%	32 100%	36 100%	40 100%	44 100%	48 100%	52 100%	56 100%	60 100%	64 100%
4	13 100%	25 100%	41 100%	61 100%	85 100%	113 100%	145 100%	181 100%	221 100%	265 100%	313 100%	365 100%	421 100%	481 100%	545 100%
5	16 100%	36 100%	64 100%	100 100%	144 100%	196 100%	256 100%	324 100%	400 100%	484 100%	576 100%	676 100%	784 100%	900 100%	1024 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%	2 943 100%	3 629 100%	4 431 100%	5 357 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%	5 928 88%	7 392 88%	9 080 89%	11 008 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%	22 569 75%	29 961 75%	39 041 75%	50 049 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%	39 210 74%	52 530 74%	69 002 74%	89 090 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%	124 515 62%	177 045 62%	246 047 62%	335 137 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%	209 820 61%	301 560 61%	423 092 61%	581 184 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%	579 125 51%	880 685 51%	1 303 777 51%	1 884 961 51%
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%	596 610 50%	948 430 50%	1 459 810 50%	2 184 462 50%	3 188 738 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%	224 143 46%	433 905 45%	795 455 44%	1 392 065 43%	2 340 495 43%	3 800 305 42%	5 984 767 42%	9 173 505 42%
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 36%	598 417 34%	1 462 563 33%	3 317 445 33%	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