Difference between revisions of "The Degree Diameter Problem for General Digraphs"
From Combinatorics Wiki
CW>Eyal 
m (1 revision imported) 
(No difference)

Latest revision as of 14:39, 3 January 2019
Contents
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 outdegree 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 nonexistence of digraphs
whose order is close to the directed Moore bounds DM(d,k)=(d^{k+1}1)(d2)^{1}.
Increasing the lower bounds for DN(d,k)
Considering constructions of large digraphs, the best results are obtained by Alegre digraph and its line digraphs, and by Kautz digraphs. Indeed, for maximum outdegree d=2 and diameter k≥4, the lower bounds 25×2^{k4} are provided by the Alegre digraph and its line digraphs, while for the other combinations of d and k, the lower bounds d^{k}+d^{k1} are provided by Kautz digraphs.
Below is the table of the largest known digraphs (as of October 2008) in the degree diameter problem for digraphs of outdegree at most 3 ≤ d ≤ 16 and diameter 2 ≤ k ≤ 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 open problem.
Table of the orders of the largest known digraphs for the directed degree diameter problem
Digraphs in bold are optimal.
[math]d[/math]\[math]k[/math]  2  3  4  5  6  7  8  9  10 
2  6  12  25  50  100  200  400  800  1600 
3  12  36  108  324  972  2 916  8 748  26 244  78 732 
4  20  80  320  1 280  5 120  20 480  81 920  327 680  1 310 720 
5  30  150  750  3 750  18 750  93 750  468 750  2 343 750  11 718 750 
6  42  252  1 512  9 072  54 432  326 592  1 959 552  11 757 312  70 543 872 
7  56  392  2 744  19 208  134 456  941 192  6 588 344  46 118 408  322 828 856 
8  72  576  4 608  36 864  294 912  2 359 296  18 874 368  150 994 944  1 207 959 552 
9  90  810  7 290  65 610  590 490  5 314 410  47 829 690  430 467 210  3 874 204 890 
10  110  1 100  11 000  110 000  1 100 000  11 000 000  110 000 000  1 100 000 000  11 000 000 000 
11  132  1 452  15 972  175 692  1 932 612  21 258 732  233 846 052  2 572 306 572  28 295 372 292 
12  156  1 872  22 464  269 568  3 234 816  38 817 792  465 813 504  5 589 762 048  67 077 144 576 
13  182  2 366  30 758  399 853  5 198 102  67 575 326  878 479 238  11 420 230 094  148 462 991 222 
The following table is the key to the colors in the table presented above:
Color  Details 
*  Alegre digraph and the corresponding line digraphs. 
*  Kautz digraphs. 
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≥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 outdegree d, diameter k and order DM(d,k)δ for small δ. The parameter δ is called the defect. Such digraphs are called (d,k,δ)digraphs.
This research direction represents a very open reseach area.
For δ=1 Gimbert proved that line digraphs of complete digraphs are the only (d,2,1)digraphs for d≥3. Miller and Fris showed the nonexistence of (2,k,1)digraphs for k≥3, while Baskoro, Miller, Širáň and Sutton proved the nonexistence of (3,k,1)digraphs for k≥3. Conde, Gimbert, Gonzalez, Miret and Moreno proved the nonexistence of (d,3,1)digraphs for d≥3.
When δ=2 Miller and Širáň proved that there exist no (2,k,2)digraphs for k≥2.
For any other combination of d, k and δ, the problem of deciding the nonexistence or otherwise of (d,k,δ)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) 112126.
 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) 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, AFCRL680668, SRI Project 7258, Final Report, pp.2028,1968.
 W.H.Kautz, Design of optimal interconnection networks for multiprocessors. Architecture and Design of Digital Computers, Nato Advanced Summer Institute,pp.249272,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, PDF version.
 J. Plesnik and S. Znam, Strongly geodetic directed graphs, Acta F. R. N. Univ. Comen.  Mathematica XXIX (1974) 29–34.
External links
 Degree Diameter online table.