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

From Combinatorics Wiki
Line 3: Line 3:
 
<center>  
 
<center>  
 
{| border="1" cellspacing="2" cellpadding="2" style="text-align: center;"
 
{| border="1" cellspacing="2" cellpadding="2" style="text-align: center;"
−
| '''<math>d</math>\<math>k</math>'''||  '''2''' ||  '''3''' ||  '''4'''|| '''5''' ||  '''6''' || '''7''' ||  '''8''' ||  '''9''' ||  '''10'''  
+
| '''<math>d</math>\<math>k</math>'''||  '''2''' ||  '''3''' ||  '''4'''|| '''5''' ||  '''6''' || '''7''' ||  '''8''' ||  '''9''' ||  '''10'''  ||  '''11'''  ||  '''12'''  
 
|-
 
|-
−
| '''3''' ||style="background-color: #bbffff;" | '''8'''||style="background-color: #bbffff;" | '''12'''||style="background-color: #bbffff;" | '''16''' ||style="background-color: #bbffff;" | '''20''' ||style="background-color: #bbffff;" | '''24''' ||style="background-color: #bbffff;" | '''28'''||style="background-color: #bbffff;" | '''32''' ||style="background-color: #bbffff;" | '''36''' || style="background-color: #bbffff;" | '''40'''
+
| '''3''' ||style="background-color: #bbffff;" | '''8'''||style="background-color: #bbffff;" | '''12'''||style="background-color: #bbffff;" | '''16''' ||style="background-color: #bbffff;" | '''20''' ||style="background-color: #bbffff;" | '''24''' ||style="background-color: #bbffff;" | '''28'''||style="background-color: #bbffff;" | '''32''' ||style="background-color: #bbffff;" | '''36''' || style="background-color: #bbffff;" | '''40'''  ||style="background-color: #bbffff;" | '''44'''||style="background-color: #bbffff;" | '''48'''
 
|-
 
|-
−
| '''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'''  
+
| '''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'''  
 
|-
 
|-
−
| '''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'''  
+
| '''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'''  
 
|-
 
|-
−
| '''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'''  
+
| '''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'''  
 
|-
 
|-
−
| '''7''' ||style="background-color: magenta;" | '''26''' ||style="background-color: magenta;" | '''76'''  ||style="background-color: magenta;" | '''160''' ||style="background-color: magenta;" | '''308''' ||style="background-color: magenta;" | '''536''' ||style="background-color: magenta;" | '''828''' ||style="background-color: magenta;" | '''1 232''' ||style="background-color: magenta;" | '''1 764''' ||style="background-color: magenta;" | '''2 392'''  
+
| '''7''' ||style="background-color: magenta;" | '''26''' ||style="background-color: magenta;" | '''76'''  ||style="background-color: magenta;" | '''160''' ||style="background-color: magenta;" | '''308''' ||style="background-color: magenta;" | '''536''' ||style="background-color: magenta;" | '''828''' ||style="background-color: magenta;" | '''1 232''' ||style="background-color: magenta;" | '''1 764''' ||style="background-color: magenta;" | '''2 392''' ||style="background-color: magenta;" | '''3 180''' ||style="background-color: magenta;" | '''4 144'''  
 
|-
 
|-
−
| '''8''' ||style="background-color: #81BEF7;" | '''35''' ||style="background-color: #CCFF00;" | '''104''' ||style="background-color: #CCFF00;" | '''248''' ||style="background-color: #CCFF00;" | '''528''' ||style="background-color: #66ff66;" | '''984''' ||style="background-color: #66ff66;" | '''1 712''' ||style="background-color: #66ff66;" | 2 768 ||style="background-color: #66ff66;" | 4 280 ||style="background-color: #66ff66;" | 6 320   
+
| '''8''' ||style="background-color: #81BEF7;" | '''35''' ||style="background-color: #CCFF00;" | '''104''' ||style="background-color: #CCFF00;" | '''248''' ||style="background-color: #CCFF00;" | '''528''' ||style="background-color: #66ff66;" | '''984''' ||style="background-color: #66ff66;" | '''1 712''' ||style="background-color: #66ff66;" | 2 768 ||style="background-color: #66ff66;" | 4 280 ||style="background-color: #66ff66;" | 6 320  ||style="background-color: #66ff66;" | 9 048 ||style="background-color: #66ff66;" | 12 552
 
|-
 
|-
−
| '''9''' ||style="background-color: #81BEF7;" | '''42''' || style="background-color: #66cc66;" | '''130''' ||style="background-color: #CCFF00;" | '''320''' ||style="background-color: #66ff66;" | '''700''' ||style="background-color: #66ff66;" | '''1 416''' ||style="background-color: #66ff66;" | 2 548 ||style="background-color: #66ff66;" | 4 304 ||style="background-color: #66ff66;" | 6 804 ||style="background-color: #66ff66;" | 10 320   
+
| '''9''' ||style="background-color: #81BEF7;" | '''42''' || style="background-color: #66cc66;" | '''130''' ||style="background-color: #CCFF00;" | '''320''' ||style="background-color: #66ff66;" | '''700''' ||style="background-color: #66ff66;" | '''1 416''' ||style="background-color: #66ff66;" | 2 548 ||style="background-color: #66ff66;" | 4 304 ||style="background-color: #66ff66;" | 6 804 ||style="background-color: #66ff66;" | 10 320  ||style="background-color: #66ff66;" | 15 004 ||style="background-color: #66ff66;" | 21 192
 
|-
 
|-
−
| '''10''' ||style="background-color: #81BEF7;" | '''51''' || style="background-color: #66cc66;" | '''177''' ||style="background-color: yellow;" | '''457''' ||style="background-color: #66ff66;" | '''1 099''' ||style="background-color: orange;" | 2 380 ||style="background-color: orange;" | 4 551 ||style="background-color: orange;" | 8 288 ||style="background-color: orange;" | 14 099 ||style="background-color: orange;" | 22 805  
+
| '''10''' ||style="background-color: #81BEF7;" | '''51''' || style="background-color: #66cc66;" | '''177''' ||style="background-color: yellow;" | '''457''' ||style="background-color: #66ff66;" | '''1 099''' ||style="background-color: orange;" | 2 380 ||style="background-color: orange;" | 4 551 ||style="background-color: orange;" | 8 288 ||style="background-color: orange;" | 14 099 ||style="background-color: orange;" | 22 805 ||style="background-color: #66ff66;" | 35 568  ||style="background-color: #66ff66;" | 53 025
 
|-
 
|-
−
| '''11''' ||style="background-color: #81BEF7;" | '''56''' ||style="background-color: yellow;" | '''210''' || style="background-color: yellow;" | '''576''' ||style="background-color: orange;" | 1 428 ||style="background-color: orange;" | 3 200 ||style="background-color: orange;" | 6 652 ||style="background-color: orange;" | 12 416 || style="background-color: orange;" | 21 572 ||style="background-color: orange;" |  35 880
+
| '''11''' ||style="background-color: #81BEF7;" | '''56''' ||style="background-color: yellow;" | '''210''' || style="background-color: yellow;" | '''576''' ||style="background-color: orange;" | 1 428 ||style="background-color: orange;" | 3 200 ||style="background-color: orange;" | 6 652 ||style="background-color: orange;" | 12 416 || style="background-color: orange;" | 21 572 ||style="background-color: orange;" |  35 880 ||style="background-color: #66ff66;" | 56 700  ||style="background-color: #66ff66;" | 87 248
 
|-
 
|-
−
| '''12''' ||style="background-color: #81BEF7;" | '''67''' ||style="background-color: yellow;" | '''275''' ||style="background-color: orange;" | 819 ||style="background-color: #66ff66;" | 2 120 ||style="background-color: #66ff66;" | 5 044 ||style="background-color: #66ff66;" | 10 777 ||style="background-color: #66ff66;" | 21 384  ||style="background-color: #66ff66;" | 39 996 ||style="background-color: #66ff66;" | 69 965
+
| '''12''' ||style="background-color: #81BEF7;" | '''67''' ||style="background-color: yellow;" | '''275''' ||style="background-color: orange;" | 819 ||style="background-color: #66ff66;" | 2 120 ||style="background-color: #66ff66;" | 5 044 ||style="background-color: #66ff66;" | 10 777 ||style="background-color: #66ff66;" | 21 384  ||style="background-color: #66ff66;" | 39 996 ||style="background-color: #66ff66;" | 69 965 ||style="background-color: #66ff66;" | 117 712  ||style="background-color: #66ff66;" | 190 392
 
|-
 
|-
−
| '''13''' ||style="background-color: #81BEF7;" | '''80''' ||style="background-color: yellow;" | '''312''' ||style="background-color: orange;" | 970 ||style="background-color: #66ff66;" | 2 676 ||style="background-color: #66ff66;" | 6 256 ||style="background-color: #66ff66;" | 14 740 ||style="background-color: #66ff66;" | 30 760  ||style="background-color: #66ff66;" | 57 396 ||style="background-color: #66ff66;" | 106 120
+
| '''13''' ||style="background-color: #81BEF7;" | '''80''' ||style="background-color: yellow;" | '''312''' ||style="background-color: orange;" | 970 ||style="background-color: #66ff66;" | 2 676 ||style="background-color: #66ff66;" | 6 256 ||style="background-color: #66ff66;" | 14 740 ||style="background-color: #66ff66;" | 30 760  ||style="background-color: #66ff66;" | 57 396 ||style="background-color: #66ff66;" | 106 120 ||style="background-color: #66ff66;" | 182 980  ||style="background-color: #66ff66;" | 295 840
 
|-
 
|-
−
| '''14''' ||style="background-color: #81BEF7;" | '''90''' ||style="background-color: yellow;" | '''381''' || style="background-color: orange;" | 1 229 ||style="background-color: #66ff66;" | 3 695 ||style="background-color: #66ff66;" | 9 800 ||style="background-color: #66ff66;" | 23 304 ||style="background-color: #66ff66;" | 49 757 || style="background-color: #66ff66;" | 103 380 ||style="background-color: #66ff66;" |  196 689
+
| '''14''' ||style="background-color: #81BEF7;" | '''90''' ||style="background-color: yellow;" | '''381''' || style="background-color: orange;" | 1 229 ||style="background-color: #66ff66;" | 3 695 ||style="background-color: #66ff66;" | 9 800 ||style="background-color: #66ff66;" | 23 304 ||style="background-color: #66ff66;" | 49 757 || style="background-color: #66ff66;" | 103 380 ||style="background-color: #66ff66;" |  196 689 ||style="background-color: #66ff66;" | 350 700 || style="background-color: #66ff66;" | 593 989
 
|-
 
|-
−
| '''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
+
| '''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
 
|-
 
|-
−
| '''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;" | 321 780 ||style="background-color: #66ff66;" | 659 464
+
| '''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;" | 321 780 ||style="background-color: #66ff66;" | 659 464 ||style="background-color: #66ff66;" | 1 350 820  ||style="background-color: #66ff66;" | 2 479 104
 
|}
 
|}
 
</center>
 
</center>

Revision as of 18:24, 8 March 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 321 780 659 464 1 350 820 2 479 104

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 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
3
8
100%
12
100%
16
100%
20
100%
24
100%
28
100%
32
100%
36
100%
40
100%
4
13
100%
25
100%
41
100%
61
100%
85
100%
113
100%
145
100%
181
100%
221
100%
5
16
100%
36
100%
64
100%
100
100%
144
100%
196
100%
256
100%
324
100%
400
100%
6
21
100%
55
100%
117
100%
203
100%
333
100%
515
100%
737
100%
1 027
100%
1 393
100%
7
26
100%
76
100%
160
100%
308
100%
536
100%
828
100%
1 232
100%
1 764
100%
2 392
100%
8
35
100%
104
100%
248
100%
528
100%
984
100%
1 712
100%
3 649
76%
5 641
76%
8 361
76%
9
42
100%
130
100%
320
100%
700
100%
1 416
100%
3 530
72%
5 890
73%
9 290
73%
14 002
74%
10
51
100%
177
100%
681
67%
1 683
65%
3 653
65%
7 183
63%
13 073
63%
22 363
63%
36 365
63%
11
56
100%
210
100%
912
63%
2 364
60%
5 336
60%
10 836
61%
20 256
61%
35 436
61%
58 728
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%
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%
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%
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%
16
112
100%
833
62%
3 649
49%
13 073
45%
40 081
44%
108545
41%
265 729
41%
598 417
39%
1 256 465
38%

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