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) |
|||
| (One intermediate revision by the same user not shown) | |||
| 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 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. | + | 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 12: | Line 12: | ||
|- | |- | ||
| − | | '''4''' ||style="background-color: #eee;" | '''13''' ||style="background-color: # | + | | '''4''' ||style="background-color: #eee;" | '''13''' ||style="background-color: #8f0;" | 35 ||style="background-color: #eee;" | 84 || style="background-color: #8f0;" | 273 ||style="background-color: #eee;" | 513||style="background-color: #eee;" | 1 155 ||style="background-color: #eee;" | 3 080 ||style="background-color: #eee;" | 7 550 ||style="background-color: #eee;" | 17 604 |
|- | |- | ||
| '''5''' ||style="background-color: #eee;" | 18 ||style="background-color: #eee;" | 60 ||style="background-color: #eee;" | 210 ||style="background-color: #eee;" | 546||style="background-color: #eee;" | 1 640 ||style="background-color: #eee;" | 5 500 ||style="background-color: #eee;" | 16 965 ||style="background-color: #eee;" | 57 840 ||style="background-color: #eee;" | 187 056 | | '''5''' ||style="background-color: #eee;" | 18 ||style="background-color: #eee;" | 60 ||style="background-color: #eee;" | 210 ||style="background-color: #eee;" | 546||style="background-color: #eee;" | 1 640 ||style="background-color: #eee;" | 5 500 ||style="background-color: #eee;" | 16 965 ||style="background-color: #eee;" | 57 840 ||style="background-color: #eee;" | 187 056 | ||
| Line 66: | Line 66: | ||
|- | |- | ||
|style="background-color: #f80; text-align: center;" | * || See B. D. McKay, M. Miller and J. Širáň, ''A note on large graphs of diameter two and given maximum degree''. | |style="background-color: #f80; text-align: center;" | * || See B. D. McKay, M. Miller and J. Širáň, ''A note on large graphs of diameter two and given maximum degree''. | ||
| + | |- | ||
| + | |style="background-color: #8f0; text-align: center;" | * || 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''. | ||
|} | |} | ||
</center> | </center> | ||
Latest revision as of 07:49, 16 July 2023
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. |