# The Degree Diameter Problem for General Digraphs

From Combinatorics Wiki

(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)

## 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)=(dk+1-1)(d-2)-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 out-degree d=2 and diameter k≥4, the lower bounds 25×2k-4 are provided by the Alegre digraph and its line digraphs, while for the other combinations of d and k, the lower bounds dk+dk-1 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 out-degree 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 out-degree 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 non-existence of (2,k,-1)-digraphs for k≥3, while Baskoro, Miller, Širáň and Sutton proved the non-existence of (3,k,-1)-digraphs for k≥3. Conde, Gimbert, Gonzalez, Miret and Moreno proved the non-existence 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 non-existence 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) 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) 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, PDF version.
• J. Plesnik and S. Znam, Strongly geodetic directed graphs, Acta F. R. N. Univ. Comen. - Mathematica XXIX (1974) 29–34.