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)
 
(One intermediate revision by the same user not shown)
Line 3: Line 3:
 
===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 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.  
+
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 12: Line 12:
 
|-
 
|-
  
| '''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  
Line 66: Line 66:
 
|-
 
|-
 
|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: #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>
 
</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.