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) |
(→Table of the orders of the largest known vertex-transitive graphs for the undirected degree diameter problem) |
||
| Line 12: | Line 12: | ||
|- | |- | ||
| − | | '''4''' ||style="background-color: #eee;" | '''13''' ||style="background-color: #eee;" | | + | | '''4''' ||style="background-color: #eee;" | '''13''' ||style="background-color: #eee;" | 30 ||style="background-color: #eee;" | 84 || style="background-color: #eee;" | 216 ||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;" | | + | | '''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 |
|- | |- | ||
| − | | '''6''' || style="background-color: #eee;" | | + | | '''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: #0ff;" |'''50''' ||style="background-color: #eee;" | | + | | '''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;" | | + | | '''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 |
|- | |- | ||
| − | | '''9''' ||style="background-color: #eee;" | | + | | '''9''' ||style="background-color: #eee;" | 60 || style="background-color: #eee;" | 294 ||style="background-color: #eee;" | 1 550 ||style="background-color: #eee;" | 8 200 ||style="background-color: #eee;" | 45 612 ||style="background-color: #eee;" | 279 616 ||style="background-color: #eee;" | 1 686 600 ||style="background-color: #eee;" | 12 123 288 ||style="background-color: #eee;" | 65 866 350 |
|- | |- | ||
| − | | '''10''' ||style="background-color: #eee;" | | + | | '''10''' ||style="background-color: #eee;" | 72 || style="background-color: #eee;" | 406 ||style="background-color: #eee;" | 2 286 ||style="background-color: #eee;" | 13 140 ||style="background-color: #eee;" | 81 235 ||style="background-color: #eee;" | 583 083 ||style="background-color: #eee;" | 4 293 452 ||style="background-color: #eee;" | 27 997 191 ||style="background-color: #eee;" | 201 038 922 |
|- | |- | ||
| − | | '''11''' ||style="background-color: #eee;" | | + | | '''11''' ||style="background-color: #eee;" | 84 ||style="background-color: #eee;" | 486 || style="background-color: #eee;" | 2 860 ||style="background-color: #eee;" | 19 500 ||style="background-color: #eee;" | 139 446 ||style="background-color: #eee;" | 1 001 268 ||style="background-color: #eee;" | 7 442 328 || style="background-color: #eee;" | 72 933 102 ||style="background-color: #eee;" | 500 605 110 |
|- | |- | ||
| − | | '''12''' ||style="background-color: #eee;" | | + | | '''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: #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 | | '''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 | ||
Revision as of 17:54, 22 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. |