Difference between revisions of "Temp VertexTransitive"
From Combinatorics Wiki
(Created page with "This is a temporary page for tables of vertex-transitive graphs in the degree-diameter problem.") |
|||
| (10 intermediate revisions by the same user not shown) | |||
| Line 1: | Line 1: | ||
| − | This is | + | '''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 [[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> | ||
| + | {| border="1" cellspacing="2" cellpadding="2" style="text-align: center;" | ||
| + | | '''<math>d</math>\<math>k</math>'''|| '''2''' || '''3''' || '''4'''|| '''5''' || '''6''' || '''7''' || '''8''' || '''9''' || '''10''' | ||
| + | |- | ||
| + | | '''3''' || style="background-color: #f0f;" | '''10''' || style="background-color: #eee;" | '''14''' || style="background-color: #ff0;" | '''30''' ||style="background-color: #eee;" | '''60''' || style="background-color: #ff0;" | '''82''' ||style="background-color: #eee;" | '''168''' ||style="background-color: #eee;" | '''300'''||style="background-color: #ff0;" | 546 ||style="background-color: #ff0;" | 1 250 | ||
| + | |- | ||
| + | |||
| + | | '''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 | ||
| + | |- | ||
| + | | '''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;" |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 | ||
| + | |- | ||
| + | | '''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;" | 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;" | 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;" | 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 | ||
| + | |- | ||
| + | | '''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 | ||
| + | |- | ||
| + | | '''15''' ||style="background-color: #eee;" | 144 || style="background-color: #eee;" | 972 || style="background-color: #eee;" | 7 956 ||style="background-color: #eee;" | 76 518 || style="background-color: #eee;" | 787 116 ||style="background-color: #eee;" | 8 599 986 ||style="background-color: #eee;" | 88 256 520 ||style="background-color: #eee;" | 1 005 263 436 ||style="background-color: #eee;" | 10 012 349 898 | ||
| + | |- | ||
| + | | '''16''' ||style="background-color: #eee;" | 200 ||style="background-color: #eee;" | 1 155 ||style="background-color: #eee;" | 9 576 ||style="background-color: #eee;" | 100 650 || style="background-color: #eee;" | 1 125 264 || style="background-color: #eee;" | 12 500 082 ||style="background-color: #eee;" | 135 340 551 ||style="background-color: #eee;" | 1 995 790 371 ||style="background-color: #eee;" | 12 951 451 931 | ||
| + | |- | ||
| + | | '''17''' ||style="background-color: #eee;" | 200 ||style="background-color: #eee;" | 1 260 ||style="background-color: #eee;" | 12 090 ||style="background-color: #eee;" | 133 144 || style="background-color: #eee;" | 1 609 830 || style="background-color: #eee;" | 18 495 162 ||style="background-color: #eee;" | 220 990 700 ||style="background-color: #eee;" | 3 372 648 954 ||style="background-color: #eee;" | | ||
| + | |||
| + | |- | ||
| + | | '''18''' ||style="background-color: #eee;" | 200 ||style="background-color: #eee;" | 1 510 ||style="background-color: #eee;" | 15 026 ||style="background-color: #eee;" | 171 828 || style="background-color: #eee;" | 2 193 321 || style="background-color: #eee;" | 26 515 120 ||style="background-color: #eee;" | 323 037 476 ||style="background-color: #eee;" | 5 768 971 167 ||style="background-color: #eee;" | | ||
| + | |||
| + | |- | ||
| + | | '''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;" | | ||
| + | |||
| + | |- | ||
| + | | '''20''' ||style="background-color: #eee;" | 210 ||style="background-color: #eee;" | 1 958 ||style="background-color: #eee;" | 21 333 ||style="background-color: #eee;" | 281 820 || style="background-color: #eee;" | 4 040 218 || style="background-color: #eee;" | 55 625 185 ||style="background-color: #eee;" | 762 374 779 ||style="background-color: #eee;" | 12 951 451 931 ||style="background-color: #eee;" | | ||
| + | |} | ||
| + | </center> | ||
| + | |||
| + | The following table is the key to the colors in the table presented above: | ||
| + | |||
| + | <center> | ||
| + | {| border="1" cellspacing="1" cellpadding="1" style="text-align: left;" | ||
| + | |'''Color''' || style="text-align: center;" |'''Details''' | ||
| + | |- | ||
| + | |style="background-color: #eee; text-align: center;" | * || Cayley graphs; see the [[The_Degree_Diameter_Problem_for_Cayley_Graphs | separate page]] for details. | ||
| + | |- | ||
| + | |style="background-color: #f0f; text-align: center;" | * || The [https://mathworld.wolfram.com/PetersenGraph.html Petersen graph]. | ||
| + | |- | ||
| + | |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''. | ||
| + | |- | ||
| + | |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> | ||
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. |