Temp VertexTransitive

From Combinatorics Wiki

Revision as of 18:15, 19 February 2022 by Grahame (talk | contribs)

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 graph 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
* 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.