The Degree Diameter Problem for Circulant Graphs

From Combinatorics Wiki

Jump to: navigation, search

Table of the orders of the largest known circulant graphs

d\k 2 3 4 5 6 7 8 9 10
3 8 12 16 20 24 28 32 36 40
4 13 25 41 61 85 113 145 181 221
5 16 36 64 100 144 196 256 324 400
6 21 55 117 203 333 515 737 1 027 1 393
7 26 76 160 308 536 828 1 232 1 764 2 392
8 35 104 248 528 984 1 712 2 768 4 280 6 320
9 42 130 320 700 1 416 2 548 4 304 6 804 10 320
10 51 177 457 1 099 2 380 4 551 8 288 14 099 22 805
11 56 210 576 1 428 3 200 6 652 12 416 21 572 35 880
12 67 275 819 2 040 4 283 8 828 16 439 29 308 51 154
13 80 312 970 2 548 5 598 12 176 22 198 40 720 72 608
14 90 381 1 229 3 244 7 815 17 389 35 929 71 748 126 109
15 96 448 1 420 3 980 9 860 22 584 48 408 93 804 177 302
16 112 518 1 717 5 024 13 380 32 731 71 731 148 385 298 105

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

d\k 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
56%
3 910
48%
19 825
45%
40 081
41%
75 517
39%
134 245
38%
13
80
100%
312
100%
1 666
58%
4 942
52%
12 642
44%
28 814
42%
59 906
37%
115 598
35%
209 762
35%
14
90
100%
381
100%
2 241
55%
7 183
45%
19 825
39%
48 639
36%
108 545
33%
224 143
32%
433 905
29%
15
96
100%
448
100%
2 816
50%
9 424
42%
27 008
37%
68 464
33%
157 184
31%
332 688
28%
658 048
27%
16
112
100%
833
62%
1 520
47%
4 551
38%
40 081
33%
108545
30%
265 729
27%
598 417
25%
1 256 465
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