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.")
 
Line 1: Line 1:
 
This is a temporary page for tables of vertex-transitive graphs in the degree-diameter problem.
 
This is a temporary page for tables of vertex-transitive graphs in the 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 graph 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''' || '''8''' || style="background-color: #eee;" | '''14''' || style="background-color: #eee;" | '''24''' ||style="background-color: #eee;" | '''60''' || style="background-color: #eee;" | '''72''' ||style="background-color: #eee;" | '''168''' ||style="background-color: #eee;" | '''300'''||style="background-color: #eee;" | 506||style="background-color: #eee;" | 882
 +
|-
 +
 +
| '''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;" | '''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: #eee;" |'''36''' ||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: #eee;" | 112 ||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: #eee;" | 200 ||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: #FF0066; text-align: center;" | * || Graphs found by Michael J. Dinneen and Paul Hafner. More details are available in a paper by the authors.
 +
|-
 +
|style="background-color: #993300; text-align: center;" | * || Graph found by Mitjana M. and Francesc Comellas. This graph was also found independently by Michael Sampels.
 +
|-
 +
|style="background-color: #CCCCFF; text-align: center;" | * || Graph found by Wohlmuth, and shown to be optimal by Marston Conder.
 +
|-
 +
|style="background-color: #bbffff; text-align: center;" | * || Graphs found by Michael Sampels.
 +
|-
 +
|style="background-color: #ccff33; text-align: center;" | * || Graphs found (and verified as optimal in most cases) by Marston Conder. See [[Description of optimal Cayley graphs found by Marston Conder|Graphs found by Marston Conder]] for more details.
 +
|-
 +
|style="background-color: #339900; text-align: center;" | * || Optimal graph found by Marston Conder. This graph was also found independently by Eyal Loz.
 +
|-
 +
|style="background-color: #006600; text-align: center;" | * || Graph found by Eugene Curtin, and shown to be optimal by Marston Conder. This graph was also found independently by Eyal Loz.
 +
|-
 +
|style="background-color: #ff6600; text-align: center;" | * || Graphs found by Eyal Loz as part of the joint project ''The degree/diameter problem for several classes of graphs'' by E. Loz, H. Pérez-Rosés and G. Pineda-Villavicencio.
 +
|-
 +
|style="background-color: #FF9900; text-align: center;" | * || Graphs found by Eyal Loz. More details are available in a paper by Eyal Loz and Jozef Širáň.
 +
|-
 +
|style="background-color: #ffff66; text-align: center;" | * || Graphs found by Eyal Loz and Guillermo Pineda-Villavicencio. More details are available in a paper by the authors.
 +
|-
 +
|style="background-color: #ff9999; text-align: center;" | * || Graph found by P. Potočnik, P. Spiga and G. Verret, ''Cubic vertex-transitive graphs on up to 1280 vertices''.
 +
|-
 +
|style="background-color: yellow; text-align: center;" | * || Graphs found by Marcel Abas.
 +
|}
 +
</center>

Revision as of 18:15, 19 February 2022

This is a temporary page for tables of vertex-transitive graphs in the 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 graph 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 8 14 24 60 72 168 300 506 882
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 36 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 112 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 200 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
* Graphs found by Michael J. Dinneen and Paul Hafner. More details are available in a paper by the authors.
* Graph found by Mitjana M. and Francesc Comellas. This graph was also found independently by Michael Sampels.
* Graph found by Wohlmuth, and shown to be optimal by Marston Conder.
* Graphs found by Michael Sampels.
* Graphs found (and verified as optimal in most cases) by Marston Conder. See Graphs found by Marston Conder for more details.
* Optimal graph found by Marston Conder. This graph was also found independently by Eyal Loz.
* Graph found by Eugene Curtin, and shown to be optimal by Marston Conder. This graph was also found independently by Eyal Loz.
* Graphs found by Eyal Loz as part of the joint project The degree/diameter problem for several classes of graphs by E. Loz, H. Pérez-Rosés and G. Pineda-Villavicencio.
* Graphs found by Eyal Loz. More details are available in a paper by Eyal Loz and Jozef Širáň.
* Graphs found by Eyal Loz and Guillermo Pineda-Villavicencio. More details are available in a paper by the authors.
* Graph found by P. Potočnik, P. Spiga and G. Verret, Cubic vertex-transitive graphs on up to 1280 vertices.
* Graphs found by Marcel Abas.
Retrieved from ‘http://combinatoricswiki.org/index.php?title=Temp_VertexTransitive&oldid=652’