|
|
Line 39: |
Line 39: |
| | '''19''' ||style="background-color: orange;" | '''156''' ||style="background-color: gold;" | ||style="background-color: gold;" | ||style="background-color: #66ff66;" | 9 652 ||style="background-color: #66ff66;" | 29 928 ||style="background-color: #66ff66;" | 99 420 ||style="background-color: #66ff66;" | 257 144 ||style="background-color: #66ff66;" | 652 004 ||style="background-color: #66ff66;" | 1 388 608 ||style="background-color: #66ff66;" | 3 101 860 ||style="background-color: #66ff66;" | 6 037 496 | | | '''19''' ||style="background-color: orange;" | '''156''' ||style="background-color: gold;" | ||style="background-color: gold;" | ||style="background-color: #66ff66;" | 9 652 ||style="background-color: #66ff66;" | 29 928 ||style="background-color: #66ff66;" | 99 420 ||style="background-color: #66ff66;" | 257 144 ||style="background-color: #66ff66;" | 652 004 ||style="background-color: #66ff66;" | 1 388 608 ||style="background-color: #66ff66;" | 3 101 860 ||style="background-color: #66ff66;" | 6 037 496 |
| |- | | |- |
− | | '''20''' ||style="background-color: orange;" | '''171''' ||style="background-color: gold;" | ||style="background-color: gold;" | 2 828 ||style="background-color: #66ff66;" | 12 396 ||style="background-color: #66ff66;" | 39 733 ||style="background-color: #66ff66;" | 131 835 ||style="background-color: #66ff66;" | 358 089 ||style="background-color: #66ff66;" | 930 184 ||style="background-color: #66ff66;" | 2 232 648 ||style="background-color: #66ff66;" | 4 529 265 ||style="background-color: #66ff66;" | 10 001 820 | + | | '''20''' ||style="background-color: orange;" | '''171''' ||style="background-color: ;" | ||style="background-color: #66ff66;" | 2 828 ||style="background-color: #66ff66;" | 12 396 ||style="background-color: #66ff66;" | 39 733 ||style="background-color: #66ff66;" | 131 835 ||style="background-color: #66ff66;" | 358 089 ||style="background-color: #66ff66;" | 930 184 ||style="background-color: #66ff66;" | 2 232 648 ||style="background-color: #66ff66;" | 4 529 265 ||style="background-color: #66ff66;" | 10 001 820 |
| |} | | |} |
| </center> | | </center> |
Revision as of 13:50, 7 June 2019
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 |
|
2 645 |
8 248 |
27 273 |
77 577 |
205 601 |
483 523 |
1 024 915 |
2 202 955 |
4 388 640
|
19 |
156 |
|
|
9 652 |
29 928 |
99 420 |
257 144 |
652 004 |
1 388 608 |
3 101 860 |
6 037 496
|
20 |
171 |
|
2 828 |
12 396 |
39 733 |
131 835 |
358 089 |
930 184 |
2 232 648 |
4 529 265 |
10 001 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
|
|
|
|
|
|
|
|
|
|
|
|
4
|
|
|
|
|
|
|
|
|
|
|
|
5
|
|
|
|
|
|
|
|
|
|
|
|
6
|
|
|
|
|
|
|
|
|
|
|
|
7
|
|
|
|
|
|
|
|
|
|
|
|
8
|
|
|
|
|
|
|
|
|
|
|
|
9
|
|
|
|
|
|
|
|
|
|
|
|
10
|
|
|
|
|
|
|
|
|
|
|
|
11
|
|
|
|
|
|
|
|
|
|
|
|
12
|
|
|
|
|
|
|
|
|
|
|
|
13
|
|
|
|
|
|
|
|
|
|
|
|
14
|
|
|
|
|
|
|
|
|
|
|
|
15
|
|
|
|
|
|
|
|
|
|
|
|
16
|
|
|
|
|
|
|
|
|
|
|
|
17
|
|
|
|
|
|
|
|
|
|
|
|
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