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
234567891011
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. 1 2 3 4 5 6 7 8 9 10 11 12 Family of digraphs found by Kautz (1969).
  2. 1 2 3 4 Cayley digraphs found by Michael J. Dinneen. Details about these graphs are available in a paper by the author.
  3. 1 2 3 Cayley digraphs found by Michael J. Dinneen. The complete set of Cayley digraphs in that order was found by Eyal Loz.
  4. 1 2 3 Cayley digraphs found by Paul Hafner. Details about these graphs are available in a paper by the author.
  5. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 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. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 Digraphs found by Comellas & Fiol (1995).
  9. 1 2 3 4 5 6 7 8 9 10 Cayley digraphs found by Eyal Loz. More details are available in Loz & Širáň (2008).
  10. 1 2 3 4 5 6 7 8 9 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
This page is issued from Wikipedia. The text is available under Creative Commons Attribution-Share Alike 4.0 unless otherwise noted. Additional terms may apply for the media files.