Temp VertexTransitive

From Combinatorics Wiki

Revision as of 18:00, 24 February 2022 by Grahame (talk | contribs) (Table of the orders of the largest known vertex-transitive graphs for the undirected degree diameter problem)

NB This page is incomplete and still under construction.

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 10 14 30 60 82 168 300 546 1 250
4 13 35 84 273 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 50 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 162 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 338 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 separate page for details.
* The Petersen graph.
* See P. Potočnik, P. Spiga and G. Verret, Cubic vertex-transitive graphs on up to 1280 vertices.
* The Hoffman-Singleton graph.
* See B. D. McKay, M. Miller and J. Širáň, A note on large graphs of diameter two and given maximum degree.
* See P. Potočnik, P. Spiga and G. Verret, Bounding the order of the vertex-stabiliser in 3-valent vertex transitive and 4-valent arc-transitive graphs.