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 610202772144171336504737
3 1227601653331 1522 0415 11511 56841 472
4 20601684651 3787 20014 40042 309137 370648 000
5 301203601 1523 77528 80086 400259 2001 010 6585 184 000
6 422108402 5209 02088 200352 8001 411 2005 184 00027 783 000
7 563361 6806 72020 160225 7921 128 9605 644 80027 783 000113 799 168
8 725043 02415 12060 480508 0323 048 19218 289 152113 799 168457 228 800
9 907205 04030 240151 2001 036 8007 257 60050 803 200384 072 1921 828 915 200
10 1109907 92055 400332 6401 960 20015 681 600125 452 8001 119 744 0006 138 320 000
11 1321 32011 88095 040665 2803 991 68031 152 000282 268 8002 910 897 00018 065 203 200
12 1561 71617 160154 4401 235 5208 648 64058 893 120588 931 2006 899 904 00047 703 427 200
13 1822 18424 024240 2402 162 16017 297 280121 080 9601 154 305 15215 159 089 098115 430 515 200

Key to colors

ColorDetails
*Family of digraphs found by W.H.Kautz. More details are available in a paper by the author.
*Family of digraphs found by V.Faber and J.W.Moore. More details are available also by other authors.
*Digraph found by V.Faber and J.W.Moore. The complete set of cayley digraphs in that order was found by Eyal Loz.
*Digraphs found by Francesc Comellas and M. A. Fiol. More details are available in a paper by the authors.
*Cayley digraphs found by Michael J. Dinneen. Details about this graph are available in a paper by the author.
*Cayley digraphs found by Michael J. Dinneen. The complete set of cayley digraphs in that order was found by Eyal Loz.
*Cayley digraphs found by Paul Hafner. Details about this graph are available in a paper by the author.
*Cayley digraph found by Paul Hafner. The complete set of cayley digraphs in that order was found by Eyal Loz.
*Digraphs found by J. Gómez.
*Cayley digraphs found by Eyal Loz. More details are available in a paper by Eyal Loz and Jozef Širáň.

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 article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.