Difference between revisions of "Temp VertexTransitive"

From Combinatorics Wiki
 
(9 intermediate revisions by the same user not shown)
Line 1: Line 1:
−
This is a temporary page for tables of vertex-transitive graphs in the degree-diameter problem.
+
'''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===
 
===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.  
+
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 9: Line 9:
 
| '''<math>d</math>\<math>k</math>'''||  '''2''' ||  '''3''' ||  '''4'''|| '''5''' ||  '''6''' || '''7''' ||  '''8''' ||  '''9''' ||  '''10'''  
 
| '''<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
+
| '''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: #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  
+
| '''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  
 
|-
 
|-
−
| '''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: #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  
+
| '''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   
 
|-
 
|-
−
| '''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   
+
| '''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  
+
| '''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
+
| '''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
+
| '''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
+
| '''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: #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;" |  
+
| '''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 57: Line 57:
 
|'''Color''' || style="text-align: center;" |'''Details'''
 
|'''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: #eee; text-align: center;" | * || Cayley graphs; see the [[The_Degree_Diameter_Problem_for_Cayley_Graphs | separate page]] for details.
 
|-
 
|-
−
|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: #f0f; text-align: center;" | * || The [https://mathworld.wolfram.com/PetersenGraph.html Petersen graph].
 
|-
 
|-
−
|style="background-color: #CCCCFF; text-align: center;" | * || Graph found by Wohlmuth, and shown to be optimal by Marston Conder.
+
|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: #bbffff; text-align: center;" | * || Graphs found by Michael Sampels.
+
|style="background-color: #0ff; text-align: center;" | * || The [https://mathworld.wolfram.com/Hoffman-SingletonGraph.html Hoffman-Singleton graph].
 
|-
 
|-
−
|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: #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: #339900; text-align: center;" | * || Optimal graph found by Marston Conder. This graph was also found independently by Eyal Loz.
+
|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''.
−
|-
 
−
|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>
 
</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.
Retrieved from ‘http://combinatoricswiki.org/index.php?title=Temp_VertexTransitive&oldid=719’