Langbahn Team – Weltmeisterschaft

Table of vertex-symmetric digraphs

The best known vertex transitive digraphs (as of October 2008) in the directed Degree diameter problem are tabulated below.

Table of the orders of the largest known vertex-symmetric graphs for the directed degree diameter problem

k
d
 2 3 4 5 6 7 8 9 10 11
2 6[g 1] 10[g 2] 20[g 3] 27[g 3] 72[g 4] 144[g 4] 171[g 2] 336[g 5] 504[g 5] 737[g 2]
3 12[g 1] 27[g 3] 60[g 6] 165[g 7] 333[g 2] 1 152[g 8] 2 041[g 9] 5 115[g 9] 11 568[g 9] 41 472[g 8]
4 20[g 1] 60[g 5] 168[g 4] 465[g 9] 1 378[g 9] 7 200[g 8] 14 400[g 10] 42 309[g 9] 137 370[g 9] 648 000[g 8]
5 30[g 1] 120[g 5] 360[g 5] 1 152[g 8] 3 775[g 9] 28 800[g 8] 86 400[g 10] 259 200[g 8] 1 010 658[g 9] 5 184 000[g 8]
6 42[g 1] 210[g 5] 840[g 5] 2 520[g 5] 9 020[g 9] 88 200[g 8] 352 800[g 10] 1 411 200[g 8] 5 184 000[g 8] 27 783 000[g 8]
7 56[g 1] 336[g 5] 1 680[g 5] 6 720[g 5] 20 160[g 5] 225 792[g 8] 1 128 960[g 10] 5 644 800[g 8] 27 783 000[g 8] 113 799 168[g 8]
8 72[g 1] 504[g 5] 3 024[g 5] 15 120[g 5] 60 480[g 5] 508 032[g 8] 3 048 192[g 10] 18 289 152[g 8] 113 799 168[g 8] 457 228 800[g 8]
9 90[g 1] 720[g 5] 5 040[g 5] 30 240[g 5] 151 200[g 5] 1 036 800[g 8] 7 257 600[g 10] 50 803 200[g 8] 384 072 192[g 8] 1 828 915 200[g 8]
10 110[g 1] 990[g 5] 7 920[g 5] 55 400[g 5] 332 640[g 5] 1 960 200[g 8] 15 681 600[g 10] 125 452 800[g 8] 1 119 744 000[g 8] 6 138 320 000[g 8]
11 132[g 1] 1 320[g 5] 11 880[g 5] 95 040[g 5] 665 280[g 5] 3 991 680[g 5] 31 152 000[g 10] 282 268 800[g 8] 2 910 897 000[g 8] 18 065 203 200[g 8]
12 156[g 1] 1 716[g 5] 17 160[g 5] 154 440[g 5] 1 235 520[g 5] 8 648 640[g 5] 58 893 120[g 10] 588 931 200[g 8] 6 899 904 000[g 8] 47 703 427 200[g 8]
13 182[g 1] 2 184[g 5] 24 024[g 5] 240 240[g 5] 2 162 160[g 5] 17 297 280[g 5] 121 080 960[g 5] 1 154 305 152[g 8] 15 159 089 098[g 8] 115 430 515 200[g 8]

The footnotes in the table indicate the origin of the digraph that achieves the given number of vertices:

  1. ^ a b c d e f g h i j k l Family of digraphs found by Kautz (1969).
  2. ^ a b c d Cayley digraphs found by Michael J. Dinneen. Details about these graphs are available in a paper by the author.
  3. ^ a b c Cayley digraphs found by Michael J. Dinneen. The complete set of Cayley digraphs in that order was found by Eyal Loz.
  4. ^ a b c Cayley digraphs found by Paul Hafner. Details about these graphs are available in a paper by the author.
  5. ^ a b c d e f g h i j k l m n o p q r s t u v w x y z aa ab ac ad ae af ag ah ai aj ak al am an Family of digraphs found by Faber & Moore (1988).
  6. ^ Digraph found by Faber & Moore (1988). The complete set of Cayley digraphs in that order was found by Eyal Loz.
  7. ^ Cayley digraph found by Paul Hafner. The complete set of Cayley digraphs in that order was found by Eyal Loz.
  8. ^ a b c d e f g h i j k l m n o p q r s t u v w x y z aa ab ac ad ae af ag ah ai aj ak Digraphs found by Comellas & Fiol (1995).
  9. ^ a b c d e f g h i j Cayley digraphs found by Eyal Loz. More details are available in Loz & Širáň (2008).
  10. ^ a b c d e f g h i Digraphs found by J. Gómez.

References

  • Kautz, W.H. (1969), "Design of optimal interconnection networks for multiprocessors", Architecture and Design of Digital Computers, Nato Advanced Summer Institute: 249–272
  • Faber, V.; Moore, J.W. (1988), "High-degree low-diameter interconnection networks with vertex symmetry:the directed case", Technical Report LA-UR-88-1051, los Alamos National Laboratory
  • Comellas, F.; Fiol, M.A. (1995), "Vertex-symmetric digraphs with small diameter", Discrete Applied Mathematics, 58 (1): 1–12, doi:10.1016/0166-218X(93)E0145-O
Quelle: Https://en.wikipedia.org/wiki/Table_of_vertex-symmetric_digraphs