View source

==Introduction==

The '''degree/diameter problem for vertex-transitive digraphs''' can be stated as follows:

''Given natural numbers ''d'' and ''k'', find the largest possible number ''DN<sup>vt</sup>(d,k)'' of vertices in a [http://en.wikipedia.org/wiki/Vertex-transitive_graph vertex-transitive digraph] of maximum out-degree ''d'' and diameter ''k''.

There are no better upper bounds for ''DN<sup>vt</sup>(d,k)'' than the very general directed ''Moore bounds'' ''DM(d,k)=(d<sup>k+1</sup>-1)(d-2)<sup>-1</sup>''. 

Therefore, in attempting to settle the values of ''DN<sup>vt</sup>(d,k)'', research activities in this problem follow the next two directions:

* Increasing the lower bounds for ''DN<sup>vt</sup>(d,k)'' by constructing ever larger vertex-transitive digraphs.

* Lowering and/or setting upper bounds for ''DN<sup>vt</sup>(d,k)'' by proving the non-existence of vertex-transitive digraphs whose order is close to the directed Moore bounds ''DM(d,k)''.

==Increasing the lower bounds for DN<sup>vt</sup>(d,k)==

Below is the table of the largest known digraphs (as of October 2008) in the [[The Degree/Diameter Problem | degree diameter problem]] for digraphs of [http://en.wikipedia.org/wiki/Outdegree out-degree] at most 3&nbsp;≤&nbsp;''d''&nbsp;≤&nbsp;16 and [http://en.wikipedia.org/wiki/Distance_(graph_theory) diameter] 2&nbsp;≤&nbsp;''k''&nbsp;≤&nbsp;10. Only a few of the vertex-transitive digraphs in this table are known to be optimal (marked in bold), and thus, finding a larger vertex-transitive digraph whose order (in terms of the order of the vertex set) is close to the directed Moore bound is considered an [http://en.wikipedia.org/wiki/Open_problem open problem]. 

===Table of the orders of the largest known vertex-symmetric graphs for the directed degree diameter problem===
Digraphs in bold are optimal.

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


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

<center>
{| border="1" cellspacing="1" cellpadding="1" style="text-align: left;"
|'''Color''' || style="text-align: center;" |'''Details'''
|-
|style="background-color: blue; text-align: center;" | * || Family of digraphs found by W.H.Kautz. More details are available in a paper by the author.
|-
|style="background-color: #6666CC; text-align: center;" | * || Family of digraphs found by V.Faber and J.W.Moore. More details are available also by other authors.
|-
|style="background-color: #669999; text-align: center;" | * || Digraph found by V.Faber and J.W.Moore. The complete set of cayley digraphs in that order was found by Eyal Loz. 
|-
|style="background-color: #990099; text-align: center;" | * || Digraphs found by Francesc Comellas and M. A. Fiol. More details are available in a paper by the authors.
|-
|style="background-color: #99FF00; text-align: center;" | * || Cayley digraphs found by Michael J. Dinneen. Details about this graph are available in a paper by the author.
|-
|style="background-color: #FF0033; text-align: center;" | * || Cayley digraphs found by Michael J. Dinneen. The complete set of cayley digraphs in that order was found by Eyal Loz. 
|-
|style="background-color: #663333; text-align: center;" | * ||  Cayley digraphs found by Paul Hafner. Details about this graph are available in a paper by the author.
|-
|style="background-color: #666633; text-align: center;" | * || Cayley digraph found by Paul Hafner. The complete set of cayley digraphs in that order was found by Eyal Loz.
|-
|style="background-color: #666666; text-align: center;" | * ||  Digraphs found by J. Gómez.
|-
|style="background-color: #FF9900; text-align: center;" | * || Cayley digraphs found by Eyal Loz. More details are available in a paper by Eyal Loz and Jozef Širáň. 
|}
</center>

==Lowering and/or setting upper bounds for DN<sup>vt</sup>(d,k)==

With the exception of the studies done for the general digraphs, no study on this research area has been identified.   

==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, [http://arxiv.org/PS_cache/math/pdf/9504/9504214v1.pdf PDF version]
* Comellas, F.; Fiol, M.A. (1995), "Vertex-symmetric digraphs with small diameter", Discrete Applied Mathematics 58: 1–12 
* Miller, Mirka; Širáň, Jozef (2005), "Moore graphs and beyond: A survey of the degree/diameter problem", Electronic Journal of Combinatorics Dynamic survey D, [http://www.combinatorics.org/Surveys/ds14.pdf PDF version]
* Loz, Eyal; Širáň, Jozef (2008), "New record graphs in the degree-diameter problem", Australasian Journal of Combinatorics 41: 63–80
==External links==
* [http://maite71.upc.es/grup_de_grafs/table_g.html Vertex-symmetric Digraphs] online table.
* [http://www.eyal.com.au/wiki/The_Degree/Diameter_Problem Eyal Loz's] Degree-Diameter problem page.




[[Category:The Degree/Diameter Problem]]