Difference between revisions of "Temp VertexTransitive"
From Combinatorics Wiki
(→Table of the orders of the largest known vertex-transitive graphs for the undirected degree diameter problem) |
|||
| Line 3: | Line 3: | ||
===Table of the orders of the largest known vertex-transitive graphs for the undirected degree diameter problem=== | ===Table of the orders of the largest known vertex-transitive graphs for the undirected degree diameter problem=== | ||
| − | Below is the table of the largest known vertex-transitive | + | Below is the table of the largest known vertex-transitive graphs in the undirected [[The Degree/Diameter Problem | degree diameter problem]] for graphs of [http://en.wikipedia.org/wiki/Degree_(graph_theory) degree] 3 ≤ ''d'' ≤ 20 and [http://en.wikipedia.org/wiki/Distance_(graph_theory) diameter] 2 ≤ ''k'' ≤ 10. All graphs which are known to be optimal are marked in bold. |
<center> | <center> | ||
| Line 56: | Line 56: | ||
{| border="1" cellspacing="1" cellpadding="1" style="text-align: left;" | {| border="1" cellspacing="1" cellpadding="1" style="text-align: left;" | ||
|'''Color''' || style="text-align: center;" |'''Details''' | |'''Color''' || style="text-align: center;" |'''Details''' | ||
| + | |- | ||
| + | |style="background-color: #eee; text-align: center;" | * || Cayley graphs; see the page for details. | ||
|- | |- | ||
|style="background-color: #FF0066; text-align: center;" | * || Graphs found by Michael J. Dinneen and Paul Hafner. More details are available in a paper by the authors. | |style="background-color: #FF0066; text-align: center;" | * || Graphs found by Michael J. Dinneen and Paul Hafner. More details are available in a paper by the authors. | ||
Revision as of 18:18, 19 February 2022
This is a temporary page for tables of vertex-transitive graphs in the degree-diameter problem.
Table of the orders of the largest known vertex-transitive graphs for the undirected degree diameter problem
Below is the table of the largest known vertex-transitive graphs in the undirected degree diameter problem for graphs of degree 3 ≤ d ≤ 20 and diameter 2 ≤ k ≤ 10. All graphs which are known to be optimal are marked in bold.
| [math]d[/math]\[math]k[/math] | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
| 3 | 8 | 14 | 24 | 60 | 72 | 168 | 300 | 506 | 882 |
| 4 | 13 | 30 | 84 | 216 | 513 | 1 155 | 3 080 | 7 550 | 17 604 |
| 5 | 18 | 60 | 210 | 546 | 1 640 | 5 500 | 16 965 | 57 840 | 187 056 |
| 6 | 32 | 108 | 375 | 1 395 | 5 115 | 19 383 | 76 461 | 307 845 | 1 253 615 |
| 7 | 36 | 168 | 672 | 2 756 | 11 988 | 52 768 | 249 660 | 1 223 050 | 6 007 230 |
| 8 | 48 | 253 | 1 100 | 5 060 | 23 991 | 131 137 | 734 820 | 4 243 100 | 24 897 161 |
| 9 | 60 | 294 | 1 550 | 8 200 | 45 612 | 279 616 | 1 686 600 | 12 123 288 | 65 866 350 |
| 10 | 72 | 406 | 2 286 | 13 140 | 81 235 | 583 083 | 4 293 452 | 27 997 191 | 201 038 922 |
| 11 | 84 | 486 | 2 860 | 19 500 | 139 446 | 1 001 268 | 7 442 328 | 72 933 102 | 500 605 110 |
| 12 | 96 | 605 | 3 775 | 29 470 | 229 087 | 1 999 500 | 15 924 326 | 158 158 875 | 1 225 374 192 |
| 13 | 112 | 680 | 4 788 | 40 260 | 347 126 | 3 322 080 | 29 927 790 | 233 660 788 | 2 129 329 324 |
| 14 | 128 | 873 | 6 510 | 57 837 | 530 448 | 5 600 532 | 50 128 239 | 579 328 377 | 7 041 746 081 |
| 15 | 144 | 972 | 7 956 | 76 518 | 787 116 | 8 599 986 | 88 256 520 | 1 005 263 436 | 10 012 349 898 |
| 16 | 200 | 1 155 | 9 576 | 100 650 | 1 125 264 | 12 500 082 | 135 340 551 | 1 995 790 371 | 12 951 451 931 |
| 17 | 200 | 1 260 | 12 090 | 133 144 | 1 609 830 | 18 495 162 | 220 990 700 | 3 372 648 954 | |
| 18 | 200 | 1 510 | 15 026 | 171 828 | 2 193 321 | 26 515 120 | 323 037 476 | 5 768 971 167 | |
| 19 | 200 | 1 638 | 17 658 | 221 676 | 3 030 544 | 39 123 116 | 501 001 000 | 8 855 580 344 | |
| 20 | 210 | 1 958 | 21 333 | 281 820 | 4 040 218 | 55 625 185 | 762 374 779 | 12 951 451 931 |
The following table is the key to the colors in the table presented above:
| Color | Details |
| * | Cayley graphs; see the page for details. |
| * | Graphs found by Michael J. Dinneen and Paul Hafner. More details are available in a paper by the authors. |
| * | Graph found by Mitjana M. and Francesc Comellas. This graph was also found independently by Michael Sampels. |
| * | Graph found by Wohlmuth, and shown to be optimal by Marston Conder. |
| * | Graphs found by Michael Sampels. |
| * | Graphs found (and verified as optimal in most cases) by Marston Conder. See Graphs found by Marston Conder for more details. |
| * | Optimal graph found by Marston Conder. This graph was also found independently by Eyal Loz. |
| * | Graph found by Eugene Curtin, and shown to be optimal by Marston Conder. This graph was also found independently by Eyal Loz. |
| * | Graphs found by Eyal Loz as part of the joint project The degree/diameter problem for several classes of graphs by E. Loz, H. Pérez-Rosés and G. Pineda-Villavicencio. |
| * | Graphs found by Eyal Loz. More details are available in a paper by Eyal Loz and Jozef Širáň. |
| * | Graphs found by Eyal Loz and Guillermo Pineda-Villavicencio. More details are available in a paper by the authors. |
| * | Graph found by P. Potočnik, P. Spiga and G. Verret, Cubic vertex-transitive graphs on up to 1280 vertices. |
| * | Graphs found by Marcel Abas. |