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 |
45 900 |
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 425 |
27 273 |
80 940 |
208 872 |
492 776 |
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 |
31 440 |
99 420 |
258 040 |
652 004 |
1 416 256 |
3 101 860 |
6 100 520 |
11 797 684 |
21 659 528 |
38 328 220 |
66 601 304
|
20 |
171 |
815 |
3 175 |
12 396 |
42 252 |
132 720 |
371 400 |
930 184 |
2 232 648 |
4 947 880 |
10 238 745 |
20 452 920 |
38 155 632 |
70 612 644 |
126 967 008
|
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
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
4
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
5
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
6
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
7
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
8
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
9
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
10
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
11
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
12
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
13
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
14
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
15
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
16
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
17
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
18
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
19
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
20
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
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