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^k+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×2^k-4 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^k-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.

External links

• Degree Diameter online table.