Table of vertex-symmetric digraphs

From Wikipedia, the free encyclopedia
Jump to: navigation, search

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

Below is the table of the best known vertex transitive digraphs (as of October 2008) in the directed Degree diameter problem.

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

The following table is the key to the colors in the table presented above:

Color Details
* 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[edit]

  • 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 

External links[edit]