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

From Combinatorics Wiki
 
(4 intermediate revisions by the same user not shown)
Line 9: Line 9:
 
| '''4''' ||style="background-color: beige;" | '''13'''|| style="background-color: beige;" | '''25''' ||style="background-color: beige;" | '''41''' || style="background-color: beige;" | '''61''' ||style="background-color: beige;" | '''85''' ||style="background-color: beige;" | '''113''' ||style="background-color: beige;" | '''145''' ||style="background-color: beige;" | '''181''' ||style="background-color: beige;" | '''221''' ||style="background-color: beige;" | '''265''' ||style="background-color: beige;" | '''313''' ||style="background-color: beige;" | '''365''' ||style="background-color: beige;" | '''421''' ||style="background-color: beige;" | '''481''' ||style="background-color: beige;" | '''545'''  
 
| '''4''' ||style="background-color: beige;" | '''13'''|| style="background-color: beige;" | '''25''' ||style="background-color: beige;" | '''41''' || style="background-color: beige;" | '''61''' ||style="background-color: beige;" | '''85''' ||style="background-color: beige;" | '''113''' ||style="background-color: beige;" | '''145''' ||style="background-color: beige;" | '''181''' ||style="background-color: beige;" | '''221''' ||style="background-color: beige;" | '''265''' ||style="background-color: beige;" | '''313''' ||style="background-color: beige;" | '''365''' ||style="background-color: beige;" | '''421''' ||style="background-color: beige;" | '''481''' ||style="background-color: beige;" | '''545'''  
 
|-
 
|-
−
| '''5''' ||style="background-color: white;" | '''16''' ||style="background-color: #66cc66;" | '''36''' ||style="background-color: #66cc66;" | '''64''' ||style="background-color: #66cc66;" |  '''100''' ||style="background-color: #66cc66;" | '''144''' ||style="background-color: #66cc66;" |  '''196''' ||style="background-color: #66cc66;" |  '''256''' ||style="background-color: #66cc66;" |  '''324''' ||style="background-color: #66cc66;" |  '''400''' ||style="background-color: #66cc66;" |  '''484''' ||style="background-color: #66cc66;" |  '''576''' ||style="background-color: #66cc66;" |  '''676''' ||style="background-color: #66cc66;" |  '''784''' ||style="background-color: #66cc66;" |  '''900''' ||style="background-color: #66cc66;" |  '''1 024'''  
+
| '''5''' ||style="background-color: magenta;" | '''16''' ||style="background-color: magenta;" | '''36''' ||style="background-color: magenta;" | '''64''' ||style="background-color: magenta;" |  '''100''' ||style="background-color: magenta;" | '''144''' ||style="background-color: magenta;" |  '''196''' ||style="background-color: magenta;" |  '''256''' ||style="background-color: magenta;" |  '''324''' ||style="background-color: magenta;" |  '''400''' ||style="background-color: magenta;" |  '''484''' ||style="background-color: magenta;" |  '''576''' ||style="background-color: magenta;" |  '''676''' ||style="background-color: magenta;" |  '''784''' ||style="background-color: magenta;" |  '''900''' ||style="background-color: magenta;" |  '''1 024'''  
 
|-
 
|-
 
| '''6''' ||style="background-color: magenta;" | '''21''' ||style="background-color: magenta;" | '''55''' ||style="background-color: magenta;" | '''117''' ||style="background-color: magenta;" | '''203''' ||style="background-color: magenta;" | '''333''' ||style="background-color: magenta;" | '''515''' ||style="background-color: magenta;" | '''737''' ||style="background-color: magenta;" | '''1 027''' ||style="background-color: magenta;" | '''1 393''' ||style="background-color: magenta;" | '''1 815''' ||style="background-color: magenta;" | '''2 329''' ||style="background-color: magenta;" | '''2 943''' ||style="background-color: magenta;" | '''3 629''' ||style="background-color: magenta;" | '''4 431''' ||style="background-color: magenta;" | '''5 357'''  
 
| '''6''' ||style="background-color: magenta;" | '''21''' ||style="background-color: magenta;" | '''55''' ||style="background-color: magenta;" | '''117''' ||style="background-color: magenta;" | '''203''' ||style="background-color: magenta;" | '''333''' ||style="background-color: magenta;" | '''515''' ||style="background-color: magenta;" | '''737''' ||style="background-color: magenta;" | '''1 027''' ||style="background-color: magenta;" | '''1 393''' ||style="background-color: magenta;" | '''1 815''' ||style="background-color: magenta;" | '''2 329''' ||style="background-color: magenta;" | '''2 943''' ||style="background-color: magenta;" | '''3 629''' ||style="background-color: magenta;" | '''4 431''' ||style="background-color: magenta;" | '''5 357'''  
Line 31: Line 31:
 
| '''15''' ||style="background-color: #81BEF7;" | '''96''' ||style="background-color: yellow;" | '''448''' ||style="background-color: orange;" | 1 420 ||style="background-color: #66ff66;" | 4 292 ||style="background-color: #66ff66;" | 12 232 ||style="background-color: #66ff66;" | 32 092 ||style="background-color: #66ff66;" | 68 944  ||style="background-color: #66ff66;" | 142 516 ||style="background-color: #66ff66;" | 276 928 ||style="background-color: #66ff66;" | 514 580  ||style="background-color: #66ff66;" | 908 480  ||style="background-color: #66ff66;" | 1 550 228 ||style="background-color: #66ff66;" | 2 566 712 ||style="background-color: #66ff66;" | 4 013 468  ||style="background-color: #66ff66;" | 6 155 056  
 
| '''15''' ||style="background-color: #81BEF7;" | '''96''' ||style="background-color: yellow;" | '''448''' ||style="background-color: orange;" | 1 420 ||style="background-color: #66ff66;" | 4 292 ||style="background-color: #66ff66;" | 12 232 ||style="background-color: #66ff66;" | 32 092 ||style="background-color: #66ff66;" | 68 944  ||style="background-color: #66ff66;" | 142 516 ||style="background-color: #66ff66;" | 276 928 ||style="background-color: #66ff66;" | 514 580  ||style="background-color: #66ff66;" | 908 480  ||style="background-color: #66ff66;" | 1 550 228 ||style="background-color: #66ff66;" | 2 566 712 ||style="background-color: #66ff66;" | 4 013 468  ||style="background-color: #66ff66;" | 6 155 056  
 
|-
 
|-
−
| '''16''' ||style="background-color: #81BEF7;" | '''112''' ||style="background-color: orange;" | 518 ||style="background-color: #66ff66;" | 1 788 ||style="background-color: #66ff66;" | 5 847 ||style="background-color: #66ff66;" | 17 733 ||style="background-color: #66ff66;" | 44 328 ||style="background-color: #66ff66;" | 107 748  ||style="background-color: #66ff66;" | 232 245 ||style="background-color: #66ff66;" | 479 255 ||style="background-color: #66ff66;" | 924 420  ||style="background-color: #66ff66;" | 1 702 428  ||style="background-color: #66ff66;" | 2 982 623 ||style="background-color: #66ff66;" | 5 209 347 ||style="background-color: #66ff66;" | 8 476 048  ||style="background-color: #66ff66;" | 13 588 848  
+
| '''16''' ||style="background-color: #81BEF7;" | '''112''' ||style="background-color: orange;" | 518 ||style="background-color: #66ff66;" | 1 788 ||style="background-color: #66ff66;" | 5 847 ||style="background-color: #66ff66;" | 17 733 ||style="background-color: #66ff66;" | 45 900 ||style="background-color: #66ff66;" | 107 748  ||style="background-color: #66ff66;" | 232 245 ||style="background-color: #66ff66;" | 479 255 ||style="background-color: #66ff66;" | 924 420  ||style="background-color: #66ff66;" | 1 702 428  ||style="background-color: #66ff66;" | 2 982 623 ||style="background-color: #66ff66;" | 5 209 347 ||style="background-color: #66ff66;" | 8 476 048  ||style="background-color: #66ff66;" | 13 588 848  
 
|-
 
|-
 
| '''17''' ||style="background-color: orange;" | '''130''' ||style="background-color: gold;" | 570 ||style="background-color: gold;" | 1 954 ||style="background-color: #66ff66;" | 6 468 ||style="background-color: #66ff66;" | 20 360 ||style="background-color: #66ff66;" | 57 684 ||style="background-color: #66ff66;" | 136 512  ||style="background-color: #66ff66;" | 321 780 ||style="background-color: #66ff66;" | 659 464 ||style="background-color: #66ff66;" | 1 350 820  ||style="background-color: #66ff66;" | 2 479 104  ||style="background-color: #66ff66;" | 4 557 364 ||style="background-color: #66ff66;" | 7 729 000 ||style="background-color: #66ff66;" | 13 275 108  ||style="background-color: #66ff66;" | 21 252 864  
 
| '''17''' ||style="background-color: orange;" | '''130''' ||style="background-color: gold;" | 570 ||style="background-color: gold;" | 1 954 ||style="background-color: #66ff66;" | 6 468 ||style="background-color: #66ff66;" | 20 360 ||style="background-color: #66ff66;" | 57 684 ||style="background-color: #66ff66;" | 136 512  ||style="background-color: #66ff66;" | 321 780 ||style="background-color: #66ff66;" | 659 464 ||style="background-color: #66ff66;" | 1 350 820  ||style="background-color: #66ff66;" | 2 479 104  ||style="background-color: #66ff66;" | 4 557 364 ||style="background-color: #66ff66;" | 7 729 000 ||style="background-color: #66ff66;" | 13 275 108  ||style="background-color: #66ff66;" | 21 252 864  
 
|-
 
|-
−
| '''18''' ||style="background-color: orange;" | '''138''' ||style="background-color: gold;" | 655 ||style="background-color: gold;" | 2 645 ||style="background-color: #66ff66;" | 8 248 ||style="background-color: #66ff66;" | 27 273 ||style="background-color: #66ff66;" | 80 940 ||style="background-color: #66ff66;" | 208 872  ||style="background-color: #66ff66;" | 492 776 ||style="background-color: #66ff66;" | 1 078 280 ||style="background-color: #66ff66;" | 2 202 955  ||style="background-color: #66ff66;" | 4 388 640  ||style="background-color: #66ff66;" | 8 068 383 ||style="background-color: #66ff66;" | 14 718 984 ||style="background-color: #66ff66;" | 25 609 955  ||style="background-color: #66ff66;" | 43 068 508  
+
| '''18''' ||style="background-color: orange;" | '''138''' ||style="background-color: gold;" | 655 ||style="background-color: gold;" | 2 645 ||style="background-color: #66ff66;" | 8 425 ||style="background-color: #66ff66;" | 27 273 ||style="background-color: #66ff66;" | 80 940 ||style="background-color: #66ff66;" | 208 872  ||style="background-color: #66ff66;" | 492 776 ||style="background-color: #66ff66;" | 1 078 280 ||style="background-color: #66ff66;" | 2 202 955  ||style="background-color: #66ff66;" | 4 388 640  ||style="background-color: #66ff66;" | 8 068 383 ||style="background-color: #66ff66;" | 14 718 984 ||style="background-color: #66ff66;" | 25 609 955  ||style="background-color: #66ff66;" | 43 068 508  
 
|-
 
|-
−
| '''19''' ||style="background-color: orange;" | '''156''' ||style="background-color: gold;" | 722 ||style="background-color: gold;" | 2 696 ||style="background-color: #66ff66;" | 9 652 ||style="background-color: #66ff66;" | 30 864 ||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 100 520 ||style="background-color: #66ff66;" | 11 797 684 ||style="background-color: #66ff66;" | 21 659 528 ||style="background-color: #66ff66;" | 38 156 524 ||style="background-color: #66ff66;" | 66 601 304  
+
| '''19''' ||style="background-color: orange;" | '''156''' ||style="background-color: gold;" | 722 ||style="background-color: gold;" | 2 696 ||style="background-color: #66ff66;" | 9 652 ||style="background-color: #66ff66;" | 31 440 ||style="background-color: #66ff66;" | 99 420 ||style="background-color: #66ff66;" | 258 040 ||style="background-color: #66ff66;" | 652 004 ||style="background-color: #66ff66;" | 1 416 256 ||style="background-color: #66ff66;" | 3 101 860  ||style="background-color: #66ff66;" | 6 100 520 ||style="background-color: #66ff66;" | 11 797 684 ||style="background-color: #66ff66;" | 21 659 528 ||style="background-color: #66ff66;" | 38 328 220 ||style="background-color: #66ff66;" | 66 601 304  
 
|-
 
|-
 
| '''20''' ||style="background-color: orange;" | '''171''' ||style="background-color: gold;" | 815 ||style="background-color: gold;" | 3 175 ||style="background-color: #66ff66;" | 12 396 ||style="background-color: #66ff66;" | 42 252 ||style="background-color: #66ff66;" | 132 720 ||style="background-color: #66ff66;" | 371 400  ||style="background-color: #66ff66;" | 930 184 ||style="background-color: #66ff66;" | 2 232 648 ||style="background-color: #66ff66;" | 4 947 880  ||style="background-color: #66ff66;" | 10 238 745  ||style="background-color: #66ff66;" | 20 452 920 ||style="background-color: #66ff66;" | 38 155 632 ||style="background-color: #66ff66;" | 70 612 644  ||style="background-color: #66ff66;" | 126 967 008  
 
| '''20''' ||style="background-color: orange;" | '''171''' ||style="background-color: gold;" | 815 ||style="background-color: gold;" | 3 175 ||style="background-color: #66ff66;" | 12 396 ||style="background-color: #66ff66;" | 42 252 ||style="background-color: #66ff66;" | 132 720 ||style="background-color: #66ff66;" | 371 400  ||style="background-color: #66ff66;" | 930 184 ||style="background-color: #66ff66;" | 2 232 648 ||style="background-color: #66ff66;" | 4 947 880  ||style="background-color: #66ff66;" | 10 238 745  ||style="background-color: #66ff66;" | 20 452 920 ||style="background-color: #66ff66;" | 38 155 632 ||style="background-color: #66ff66;" | 70 612 644  ||style="background-color: #66ff66;" | 126 967 008  
Line 1,352: Line 1,352:
 
| 108 545
 
| 108 545
 
|-
 
|-
−
|41%
+
|42%
 
|}
 
|}
 
| align="center" |
 
| align="center" |
Line 1,532: Line 1,532:
 
| 22 363
 
| 22 363
 
|-
 
|-
−
|37%
+
|38%
 
|}
 
|}
 
| align="center" |
 
| align="center" |
Line 1,657: Line 1,657:
 
| 4 780 008
 
| 4 780 008
 
|-
 
|-
−
|29%
+
|30%
 
|}
 
|}
 
| align="center" |
 
| align="center" |
Line 1,788: Line 1,788:
 
| 540 279 585
 
| 540 279 585
 
|-
 
|-
−
|23%
+
|24%
 
|}
 
|}
  

Latest revision as of 09:24, 24 November 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 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
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%
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%
3 732 560
42%
6 140 800
42%
9 785 072
41%
15 158 272
41%
16
112
100%
833
62%
3 649
49%
13 073
45%
40 081
44%
108 545
42%
265 729
41%
598 417
39%
1 256 465
38%
2 485 825
37%
4 673 345
36%
8 405 905
35%
14 546 705
36%
24 331 777
35%
39 490 049
34%
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%
13 079 250
35%
22 952 610
34%
38 878 482
34%
63 821 826
33%
18
138
100%
1 159
57%
5 641
47%
22 363
38%
75 517
36%
224 143
36%
598 417
35%
1 462 563
34%
3 317 445
33%
7 059 735
31%
14 218 905
31%
27 298 155
30%
50 250 765
29%
89 129 247
29%
152 951 073
28%
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
30%
10 377 180
30%
21 278 640
29%
41 517 060
28%
77 548 920
28%
139 380 012
27%
242 080 320
28%
20
171
100%
1 561
52%
8 361
38%
36 365
34%
134 245
31%
433 905
31%
1 256 465
30%
3 317 445
28%
8 097 453
28%
18 474 633
27%
39 753 273
26%
81 270 333
25%
158 819 253
24%
298 199 265
24%
540 279 585
24%

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=489’