Difference between revisions of "The Degree Diameter Problem for Circulant Graphs"

From Combinatorics Wiki
Line 80: Line 80:
 
<center>
 
<center>
 
{| border="1"
 
{| border="1"
−
| '''<math>d</math>\<math>k</math>'''|| '''2''' || '''3''' ||  '''4'''|| '''5''' ||  '''6''' || '''7''' ||  '''8''' ||  '''9''' ||  '''10''' ||  '''11''' ||  '''12'''  
+
| '''<math>d</math>\<math>k</math>'''|| '''2''' || '''3''' ||  '''4'''|| '''5''' ||  '''6''' || '''7''' ||  '''8''' ||  '''9''' ||  '''10''' ||  '''11''' ||  '''12''' ||  '''13''' ||  '''14''' ||  '''15''' ||  '''16'''  
 
|-
 
|-
 
|'''3'''
 
|'''3'''
Line 128: Line 128:
 
{| border="2" style="background:rgb(180,180,255);"  
 
{| border="2" style="background:rgb(180,180,255);"  
 
|36
 
|36
 +
|-
 +
|'''100%'''
 +
|}
 +
| align="center" |
 +
{| border="2" style="background:rgb(180,180,255);"
 +
|40
 
|-
 
|-
 
|'''100%'''
 
|'''100%'''
Line 145: Line 151:
 
| align="center" |
 
| align="center" |
 
{| border="2" style="background:rgb(180,180,255);"  
 
{| border="2" style="background:rgb(180,180,255);"  
−
|40
+
|52
 +
|-
 +
|'''100%'''
 +
|}
 +
| align="center" |
 +
{| border="2" style="background:rgb(180,180,255);"
 +
|56
 +
|-
 +
|'''100%'''
 +
|}
 +
| align="center" |
 +
{| border="2" style="background:rgb(180,180,255);"
 +
|60
 +
|-
 +
|'''100%'''
 +
|}
 +
| align="center" |
 +
{| border="2" style="background:rgb(180,180,255);"
 +
|64
 
|-
 
|-
 
|'''100%'''
 
|'''100%'''
Line 217: Line 241:
 
{| border="2" style="background:rgb(180,180,255);"  
 
{| border="2" style="background:rgb(180,180,255);"  
 
|313
 
|313
 +
|-
 +
|'''100%'''
 +
|}
 +
| align="center" |
 +
{| border="2" style="background:rgb(180,180,255);"
 +
|365
 +
|-
 +
|'''100%'''
 +
|}
 +
| align="center" |
 +
{| border="2" style="background:rgb(180,180,255);"
 +
|421
 +
|-
 +
|'''100%'''
 +
|}
 +
| align="center" |
 +
{| border="2" style="background:rgb(180,180,255);"
 +
|481
 +
|-
 +
|'''100%'''
 +
|}
 +
| align="center" |
 +
{| border="2" style="background:rgb(180,180,255);"
 +
|545
 
|-
 
|-
 
|'''100%'''
 
|'''100%'''
Line 288: Line 336:
 
{| border="2" style="background:rgb(180,180,255);"  
 
{| border="2" style="background:rgb(180,180,255);"  
 
|576
 
|576
 +
|-
 +
|'''100%'''
 +
|}
 +
| align="center" |
 +
{| border="2" style="background:rgb(180,180,255);"
 +
|676
 +
|-
 +
|'''100%'''
 +
|}
 +
| align="center" |
 +
{| border="2" style="background:rgb(180,180,255);"
 +
|784
 +
|-
 +
|'''100%'''
 +
|}
 +
| align="center" |
 +
{| border="2" style="background:rgb(180,180,255);"
 +
|900
 +
|-
 +
|'''100%'''
 +
|}
 +
| align="center" |
 +
{| border="2" style="background:rgb(180,180,255);"
 +
|1024
 
|-
 
|-
 
|'''100%'''
 
|'''100%'''
Line 359: Line 431:
 
{| border="2" style="background:rgb(180,180,255);"  
 
{| border="2" style="background:rgb(180,180,255);"  
 
|2 329
 
|2 329
 +
|-
 +
|'''100%'''
 +
|}
 +
| align="center" |
 +
{| border="2" style="background:rgb(180,180,255);"
 +
|2 943
 +
|-
 +
|'''100%'''
 +
|}
 +
| align="center" |
 +
{| border="2" style="background:rgb(180,180,255);"
 +
|3 629
 +
|-
 +
|'''100%'''
 +
|}
 +
| align="center" |
 +
{| border="2" style="background:rgb(180,180,255);"
 +
|4 431
 +
|-
 +
|'''100%'''
 +
|}
 +
| align="center" |
 +
{| border="2" style="background:rgb(180,180,255);"
 +
|5 357
 
|-
 
|-
 
|'''100%'''
 
|'''100%'''
Line 430: Line 526:
 
{| border="2" style="background:#ABCDEF;"  
 
{| border="2" style="background:#ABCDEF;"  
 
|4 672
 
|4 672
 +
|-
 +
|89%
 +
|}
 +
| align="center" |
 +
{| border="2" style="background:#ABCDEF;"
 +
|5 928
 +
|-
 +
|88%
 +
|}
 +
| align="center" |
 +
{| border="2" style="background:#ABCDEF;"
 +
|7 392
 +
|-
 +
|88%
 +
|}
 +
| align="center" |
 +
{| border="2" style="background:#ABCDEF;"
 +
|9 080
 +
|-
 +
|89%
 +
|}
 +
| align="center" |
 +
{| border="2" style="background:#ABCDEF;"
 +
|11 008
 
|-
 
|-
 
|89%
 
|89%
Line 501: Line 621:
 
{| border="2" style="background:#ABCDEF;"  
 
{| border="2" style="background:#ABCDEF;"  
 
|16 641
 
|16 641
 +
|-
 +
|75%
 +
|}
 +
| align="center" |
 +
{| border="2" style="background:#ABCDEF;"
 +
|22 569
 +
|-
 +
|75%
 +
|}
 +
| align="center" |
 +
{| border="2" style="background:#ABCDEF;"
 +
|29 961
 +
|-
 +
|75%
 +
|}
 +
| align="center" |
 +
{| border="2" style="background:#ABCDEF;"
 +
|39 041
 +
|-
 +
|75%
 +
|}
 +
| align="center" |
 +
{| border="2" style="background:#ABCDEF;"
 +
|50 049
 
|-
 
|-
 
|75%
 
|75%
Line 572: Line 716:
 
{| border="2" style="background:#ABCDEF;"  
 
{| border="2" style="background:#ABCDEF;"  
 
|28 610
 
|28 610
 +
|-
 +
|74%
 +
|}
 +
| align="center" |
 +
{| border="2" style="background:#ABCDEF;"
 +
|39 210
 +
|-
 +
|74%
 +
|}
 +
| align="center" |
 +
{| border="2" style="background:#ABCDEF;"
 +
|52 530
 +
|-
 +
|74%
 +
|}
 +
| align="center" |
 +
{| border="2" style="background:#ABCDEF;"
 +
|69 002
 +
|-
 +
|74%
 +
|}
 +
| align="center" |
 +
{| border="2" style="background:#ABCDEF;"
 +
|89 090
 
|-
 
|-
 
|74%
 
|74%
Line 643: Line 811:
 
{| border="2" style="background:#ABCDEF;"  
 
{| border="2" style="background:#ABCDEF;"  
 
|85 305
 
|85 305
 +
|-
 +
|62%
 +
|}
 +
| align="center" |
 +
{| border="2" style="background:#ABCDEF;"
 +
|124 515
 +
|-
 +
|62%
 +
|}
 +
| align="center" |
 +
{| border="2" style="background:#ABCDEF;"
 +
|177 045
 +
|-
 +
|62%
 +
|}
 +
| align="center" |
 +
{| border="2" style="background:#ABCDEF;"
 +
|246 047
 +
|-
 +
|62%
 +
|}
 +
| align="center" |
 +
{| border="2" style="background:#ABCDEF;"
 +
|335 137
 
|-
 
|-
 
|62%
 
|62%

Revision as of 15:17, 20 August 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 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%
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
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
Retrieved from ‘http://combinatoricswiki.org/index.php?title=The_Degree_Diameter_Problem_for_Circulant_Graphs&oldid=474’