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 18: | Line 18: | ||
| '''6''' || style="background-color: #eee;" |'''32'''||style="background-color: #eee;" | '''108''' ||style="background-color: #eee;" | 375 ||style="background-color: #eee;" | 1 395 ||style="background-color: #eee;" | 5 115 ||style="background-color: #eee;" | 19 383 ||style="background-color: #eee;" | 76 461 ||style="background-color: #eee;" | 307 845 ||style="background-color: #eee;" | 1 253 615 | | '''6''' || style="background-color: #eee;" |'''32'''||style="background-color: #eee;" | '''108''' ||style="background-color: #eee;" | 375 ||style="background-color: #eee;" | 1 395 ||style="background-color: #eee;" | 5 115 ||style="background-color: #eee;" | 19 383 ||style="background-color: #eee;" | 76 461 ||style="background-color: #eee;" | 307 845 ||style="background-color: #eee;" | 1 253 615 | ||
|- | |- | ||
| − | | '''7''' ||style="background-color: # | + | | '''7''' ||style="background-color: #0ff;" |'''50''' ||style="background-color: #eee;" |'''168''' ||style="background-color: #eee;" | 672 ||style="background-color: #eee;" | 2 756 ||style="background-color: #eee;" | 11 988 ||style="background-color: #eee;" | 52 768 ||style="background-color: #eee;" | 249 660 ||style="background-color: #eee;" | 1 223 050 ||style="background-color: #eee;" | 6 007 230 |
|- | |- | ||
| '''8''' ||style="background-color: #eee;" |'''48'''||style="background-color: #eee;" | 253 ||style="background-color: #eee;" | 1 100 ||style="background-color: #eee;" | 5 060 ||style="background-color: #eee;" | 23 991 ||style="background-color: #eee;" | 131 137 ||style="background-color: #eee;" | 734 820 ||style="background-color: #eee;" | 4 243 100 ||style="background-color: #eee;" | 24 897 161 | | '''8''' ||style="background-color: #eee;" |'''48'''||style="background-color: #eee;" | 253 ||style="background-color: #eee;" | 1 100 ||style="background-color: #eee;" | 5 060 ||style="background-color: #eee;" | 23 991 ||style="background-color: #eee;" | 131 137 ||style="background-color: #eee;" | 734 820 ||style="background-color: #eee;" | 4 243 100 ||style="background-color: #eee;" | 24 897 161 | ||
| Line 30: | Line 30: | ||
| '''12''' ||style="background-color: #eee;" | '''96''' ||style="background-color: #eee;" | 605 ||style="background-color: #eee;" | 3 775 ||style="background-color: #eee;" | 29 470||style="background-color: #eee;" | 229 087 ||style="background-color: #eee;" | 1 999 500 ||style="background-color: #eee;" | 15 924 326 ||style="background-color: #eee;" | 158 158 875 ||style="background-color: #eee;" | 1 225 374 192 | | '''12''' ||style="background-color: #eee;" | '''96''' ||style="background-color: #eee;" | 605 ||style="background-color: #eee;" | 3 775 ||style="background-color: #eee;" | 29 470||style="background-color: #eee;" | 229 087 ||style="background-color: #eee;" | 1 999 500 ||style="background-color: #eee;" | 15 924 326 ||style="background-color: #eee;" | 158 158 875 ||style="background-color: #eee;" | 1 225 374 192 | ||
|- | |- | ||
| − | | '''13''' ||style="background-color: # | + | | '''13''' ||style="background-color: #f80;" | 162 ||style="background-color: #eee;" | 680 ||style="background-color: #eee;" | 4 788 ||style="background-color: #eee;" |40 260 ||style="background-color: #eee;" | 347 126 ||style="background-color: #eee;" | 3 322 080 ||style="background-color: #eee;" | 29 927 790 ||style="background-color: #eee;" | 233 660 788 ||style="background-color: #eee;" | 2 129 329 324 |
|- | |- | ||
| '''14''' ||style="background-color: #eee;" | 128 ||style="background-color: #eee;" | 873 ||style="background-color: #eee;" | 6 510 ||style="background-color: #eee;" | 57 837 ||style="background-color: #eee;" | 530 448 ||style="background-color: #eee;" | 5 600 532 ||style="background-color: #eee;" | 50 128 239 ||style="background-color: #eee;" | 579 328 377 ||style="background-color: #eee;" | 7 041 746 081 | | '''14''' ||style="background-color: #eee;" | 128 ||style="background-color: #eee;" | 873 ||style="background-color: #eee;" | 6 510 ||style="background-color: #eee;" | 57 837 ||style="background-color: #eee;" | 530 448 ||style="background-color: #eee;" | 5 600 532 ||style="background-color: #eee;" | 50 128 239 ||style="background-color: #eee;" | 579 328 377 ||style="background-color: #eee;" | 7 041 746 081 | ||
| Line 44: | Line 44: | ||
|- | |- | ||
| − | | '''19''' ||style="background-color: # | + | | '''19''' ||style="background-color: #f80;" | 338 ||style="background-color: #eee;" | 1 638 ||style="background-color: #eee;" | 17 658 ||style="background-color: #eee;" | 221 676 || style="background-color: #eee;" | 3 030 544 || style="background-color: #eee;" | 39 123 116 ||style="background-color: #eee;" | 501 001 000 ||style="background-color: #eee;" | 8 855 580 344 ||style="background-color: #eee;" | |
|- | |- | ||
| Line 62: | Line 62: | ||
|- | |- | ||
|style="background-color: #ff0; text-align: center;" | * || See P. Potočnik, P. Spiga and G. Verret, ''Cubic vertex-transitive graphs on up to 1280 vertices''. | |style="background-color: #ff0; text-align: center;" | * || See P. Potočnik, P. Spiga and G. Verret, ''Cubic vertex-transitive graphs on up to 1280 vertices''. | ||
| + | |- | ||
| + | |style="background-color: #0ff; text-align: center;" | * || The [https://mathworld.wolfram.com/Hoffman-SingletonGraph.html Hoffman-Singleton graph]. | ||
| + | |- | ||
| + | |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''. | ||
|} | |} | ||
</center> | </center> | ||
Revision as of 16:20, 20 February 2022
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 | 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 | 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. |