View source for The Degree Diameter Problem for General Digraphs

==Introduction==
The '''degree/diameter problem for general digraphs''' can be stated as follows:

''Given natural numbers ''d'' and ''k'', find the largest possible number ''DN(d,k)'' of vertices in a digraph of maximum out-degree ''d'' and diameter ''k''.''

In attempting to settle the values of ''DN(d,k)'', research activities in this problem have follow the following two directions:

*Increasing the lower bounds for ''DN(d,k)'' by constructing ever larger graphs.

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

==Increasing the lower bounds for ''DN(d,k)''==

Considering constructions of large digraphs, the best results are obtained by Alegre digraph and its [http://en.wikipedia.org/wiki/Line_graph line digraphs], and by [http://en.wikipedia.org/wiki/Kautz_graph Kautz digraphs]. Indeed, for maximum out-degree ''d=2'' and diameter ''k&ge;4'', the lower bounds ''25&times;2<sup>k-4</sup>'' are provided by the Alegre digraph and its line digraphs, while for the other combinations of ''d'' and ''k'', the lower bounds ''d<sup>k</sup>+d<sup>k-1</sup>'' are provided by Kautz digraphs.

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 digraphs in this table are known to be optimal (marked in bold), and thus, finding a larger digraph whose order (in terms of the order of the vertex set) 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 digraphs for the directed degree diameter problem===
Digraphs in bold are optimal.

<center> 
{| border="1" cellspacing="2" cellpadding="2" style="text-align: center;"
| '''<math>d</math>\<math>k</math>'''||  '''2''' ||  '''3''' ||  '''4'''|| '''5''' ||  '''6''' || '''7''' ||  '''8''' ||  '''9''' ||  '''10''' 
|-
|'''2'''|| style="background-color: #66ff66; text-align: center;" |'''6''' ||style="background-color: #66ff66; text-align: center;" |	'''12''' ||style="background-color: #FF0066; text-align: center;" |	25||style="background-color: #FF0066; text-align: center;" |	50||style="background-color: #FF0066; text-align: center;" |	100||style="background-color: #FF0066; text-align: center;" |	200||style="background-color: #FF0066; text-align: center;" |	400||style="background-color: #FF0066; text-align: center;" |	800||style="background-color: #FF0066; text-align: center;" |	1600
|-
|'''3'''|| style="background-color: #66ff66; text-align: center;" |'''12''' ||style="background-color: #66ff66; text-align: center;" |	36||	style="background-color: #66ff66; text-align: center;" |108||style="background-color: #66ff66; text-align: center;" |	324	||style="background-color: #66ff66; text-align: center;" |972	||style="background-color: #66ff66; text-align: center;" |2 916||style="background-color: #66ff66; text-align: center;" |	8 748||	style="background-color: #66ff66; text-align: center;" |26 244||style="background-color: #66ff66; text-align: center;" |	78 732
|-
|'''4'''||style="background-color: #66ff66; text-align: center;" |'''20''' || style="background-color: #66ff66; text-align: center;" |80 || style="background-color: #66ff66; text-align: center;" |320 || style="background-color: #66ff66; text-align: center;" |1 280 || style="background-color: #66ff66; text-align: center;" |5 120 || style="background-color: #66ff66; text-align: center;" |20 480 || style="background-color: #66ff66; text-align: center;" |81 920 || style="background-color: #66ff66; text-align: center;" |327 680 || style="background-color: #66ff66; text-align: center;" |1 310 720
|-
|'''5'''||style="background-color: #66ff66; text-align: center;" |'''30''' || style="background-color: #66ff66; text-align: center;" |150 || style="background-color: #66ff66; text-align: center;" |750 || style="background-color: #66ff66; text-align: center;" |3 750 || style="background-color: #66ff66; text-align: center;" |18 750 || style="background-color: #66ff66; text-align: center;" |93 750 || style="background-color: #66ff66; text-align: center;" |468 750 || style="background-color: #66ff66; text-align: center;" |2 343 750 || style="background-color: #66ff66; text-align: center;" |11 718 750
|-
|'''6'''||style="background-color: #66ff66; text-align: center;" |'''42''' || style="background-color: #66ff66; text-align: center;" |252 || style="background-color: #66ff66; text-align: center;" |1 512 || style="background-color: #66ff66; text-align: center;" |9 072 || style="background-color: #66ff66; text-align: center;" |54 432 || style="background-color: #66ff66; text-align: center;" |326 592 || style="background-color: #66ff66; text-align: center;" |1 959 552 || style="background-color: #66ff66; text-align: center;" |11 757 312 || style="background-color: #66ff66; text-align: center;" |70 543 872
|-
|'''7'''||style="background-color: #66ff66; text-align: center;" |'''56'''|| style="background-color: #66ff66; text-align: center;" |392 || style="background-color: #66ff66; text-align: center;" |2 744 || style="background-color: #66ff66; text-align: center;" |19 208 || style="background-color: #66ff66; text-align: center;" |134 456 || style="background-color: #66ff66; text-align: center;" |941 192 || style="background-color: #66ff66; text-align: center;" |6 588 344 || style="background-color: #66ff66; text-align: center;" |46 118 408 || style="background-color: #66ff66; text-align: center;" |322 828 856
|-
|'''8'''||style="background-color: #66ff66; text-align: center;" |'''72''' || style="background-color: #66ff66; text-align: center;" |576 || style="background-color: #66ff66; text-align: center;" |4 608 || style="background-color: #66ff66; text-align: center;" |36 864 || style="background-color: #66ff66; text-align: center;" |294 912 || style="background-color: #66ff66; text-align: center;" |2 359 296 || style="background-color: #66ff66; text-align: center;" |18 874 368 || style="background-color: #66ff66; text-align: center;" |150 994 944 || style="background-color: #66ff66; text-align: center;" |1 207 959 552
|-
|'''9'''||style="background-color: #66ff66; text-align: center;" |'''90''' || style="background-color: #66ff66; text-align: center;" |810 || style="background-color: #66ff66; text-align: center;" |7 290 || style="background-color: #66ff66; text-align: center;" |65 610 || style="background-color: #66ff66; text-align: center;" |590 490 || style="background-color: #66ff66; text-align: center;" |5 314 410 || style="background-color: #66ff66; text-align: center;" |47 829 690 || style="background-color: #66ff66; text-align: center;" |430 467 210 || style="background-color: #66ff66; text-align: center;" |3 874 204 890
|-
|'''10'''||style="background-color: #66ff66; text-align: center;" |'''110''' || style="background-color: #66ff66; text-align: center;" |1 100 || style="background-color: #66ff66; text-align: center;" |11 000 || style="background-color: #66ff66; text-align: center;" |110 000 || style="background-color: #66ff66; text-align: center;" |1 100 000 || style="background-color: #66ff66; text-align: center;" |11 000 000 || style="background-color: #66ff66; text-align: center;" |110 000 000 || style="background-color: #66ff66; text-align: center;" |1 100 000 000 || style="background-color: #66ff66; text-align: center;" |11 000 000 000
|-
|'''11'''||style="background-color: #66ff66; text-align: center;" |'''132''' || style="background-color: #66ff66; text-align: center;" |1 452 || style="background-color: #66ff66; text-align: center;" |15 972 || style="background-color: #66ff66; text-align: center;" |175 692 || style="background-color: #66ff66; text-align: center;" |1 932 612 || style="background-color: #66ff66; text-align: center;" |21 258 732 || style="background-color: #66ff66; text-align: center;" |233 846 052 || style="background-color: #66ff66; text-align: center;" |2 572 306 572 || style="background-color: #66ff66; text-align: center;" |28 295 372 292
|-
|'''12'''||style="background-color: #66ff66; text-align: center;" |'''156''' || style="background-color: #66ff66; text-align: center;" |1 872 || style="background-color: #66ff66; text-align: center;" |22 464 || style="background-color: #66ff66; text-align: center;" |269 568 || style="background-color: #66ff66; text-align: center;" |3 234 816 || style="background-color: #66ff66; text-align: center;" |38 817 792 || style="background-color: #66ff66; text-align: center;" |465 813 504 || style="background-color: #66ff66; text-align: center;" |5 589 762 048 || style="background-color: #66ff66; text-align: center;" |67 077 144 576
|-
|'''13'''||style="background-color: #66ff66; text-align: center;" |'''182''' || style="background-color: #66ff66; text-align: center;" |2 366 || style="background-color: #66ff66; text-align: center;" |30 758 || style="background-color: #66ff66; text-align: center;" |399 853 || style="background-color: #66ff66; text-align: center;" |5 198 102 || style="background-color: #66ff66; text-align: center;" |67 575 326 || style="background-color: #66ff66; text-align: center;" |878 479 238 || style="background-color: #66ff66; text-align: center;" |11 420 230 094 || style="background-color: #66ff66; text-align: center;" |148 462 991 222
|}
</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: #FF0066; text-align: center;" | * || Alegre digraph and the corresponding line digraphs.
|-
|style="background-color: #66ff66; text-align: center;" | * || Kautz digraphs.
|}
</center>

==Lowering and/or setting upper bounds for ''DN(d,k)''==

The directed Moore bound can be reached only for trivial combinations of ''d'' and ''k'', that is, ''d=1'' or ''k=1''. For ''d=1'' the Moore digraphs are the cycles on ''k+1'' vertices (''k&ge;1''), while for ''k=1'' they are the complete digraphs of order ''d+1''. This outcome was obtained by Plesnik and Znam, and independently by Bridges and Toueg. Therefore, theoretical works have been done to determine the lowest possible upper bounds. In this direction reserachers have been interested in digraphs of maximum out-degree ''d'', diameter ''k'' and order ''DM(d,k)-&delta;'' for small ''&delta;''. The parameter ''&delta;'' is called the defect. Such digraphs are called ''(d,k,-&delta;)''-digraphs.

This research direction represents a very open reseach area.

For ''&delta;=1'' Gimbert proved that line digraphs of complete digraphs are the only ''(d,2,-1)''-digraphs for ''d&ge;3''. Miller and Fris showed the non-existence of ''(2,k,-1)''-digraphs for ''k&ge;3'', while Baskoro, Miller, Širáň and Sutton proved the non-existence of ''(3,k,-1)''-digraphs for ''k&ge;3''. Conde, Gimbert, Gonzalez, Miret and Moreno proved the non-existence of ''(d,3,-1)''-digraphs for ''d&ge;3''.

When ''&delta;=2'' Miller and Širáň proved that there exist no ''(2,k,-2)''-digraphs for ''k&ge;2''.

For any other combination of ''d'', ''k'' and ''&delta;'', the problem of deciding the non-existence or otherwise of ''(d,k,-&delta;)''-digraphs remains open.

==References==
* E.T. Baskoro, M. Miller, J. Širáň and M. Sutton, A complete characterisation of almost Moore digraphs of degree three, J. Graph Theory 48(2) (2005) 112-126.

* W.G. Bridges and S. Toueg, On the impossibility of directed Moore graphs, J. Combinatorial Theory B 29 (1980) 339–341.

* J. Conde, J. Gimbert, J. Gonzalez, J.M. Miret and R. Moreno, Nonexistence of almost Moore digraphs of diameter three, The Electronic Journal of Combinatorics 15(1) (2008) [http://www.emis.de/journals/EJC/Volume_15/PDF/v15i1r87.pdf PDF version].

* J. Gimbert, On the existence of (d, k)-digraphs, 16th British Combinatorial Conference (London, 1997), Discrete Mathematics 197/198 (1999) 375–391.

* J. Gimbert, Enumeration of almost Moore digraphs of diameter two, Discrete Mathematics 231 (2001) 177–190.

* W.H.Kautz, Bounds on directed (d,k) graphs.Theory of cellular login networks and machines, AFCRL-68-0668, SRI Project 7258, Final Report, pp.20-28,1968. 

* W.H.Kautz, Design of optimal interconnection networks for multiprocessors. Architecture and Design of Digital Computers, Nato Advanced Summer Institute,pp.249-272,1969.

* M. Miller and I. Fris, Maximum order digraphs for diameter 2 or degree 2, Pullman volume of Graphs and Matrices, Lecture Notes in Pure and Applied Mathematics 139 (1992) 269–278.

* Miller, M.; Širáň, J. (2005), "Moore graphs and beyond: A survey of the degree/diameter problem", Electronic Journal of Combinatorics, Dynamic survey, [http://www.combinatorics.org/Surveys/ds14.pdf PDF version].

* J. Plesnik and S. Znam, Strongly geodetic directed graphs, Acta F. R. N. Univ. Comen. - Mathematica XXIX (1974) 29–34.

==External links==
* [http://www-mat.upc.es/grup_de_grafs/ Degree Diameter] online table.



[[Category:The Degree/Diameter Problem]]