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. Family of digraphs found by Kautz (1969).
2. Cayley digraphs found by Michael J. Dinneen. Details about these graphs are available in a paper by the author.
3. Cayley digraphs found by Michael J. Dinneen. The complete set of Cayley digraphs in that order was found by Eyal Loz.
4. Cayley digraphs found by Paul Hafner. Details about these graphs are available in a paper by the author.
5. 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. Digraphs found by Comellas & Fiol (1995).
9. Cayley digraphs found by Eyal Loz. More details are available in Loz & Širáň (2008).
10. 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

• J. Dinneen, Michael; Hafner, Paul R. (1994), "New Results for the Degree/Diameter Problem", Networks, 24 (7): 359–367, arXiv:math/9504214, doi:10.1002/net.3230240702

• 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

• Miller, Mirka; Širáň, Jozef (2005), "Moore graphs and beyond: A survey of the degree/diameter problem" (PDF), Electronic Journal of Combinatorics, Dynamic, survey D

• Loz, Eyal; Širáň, Jozef (2008), "New record graphs in the degree-diameter problem" (PDF), Australasian Journal of Combinatorics, 41: 63–80

External links

• Vertex-symmetric Digraphs online table.
• The Degree - Diameter Problem on CombinatoricsWiki.org.
• Eyal Loz's Degree-Diameter problem page.