# The Degree Diameter Problem for Vertex Symmetric Digraphs

From Combinatorics Wiki

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

## 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 DNvt(d,k) of vertices in a vertex-transitive digraph of maximum out-degree d and diameter k.

There are no better upper bounds for DNvt(d,k) than the very general directed Moore bounds DM(d,k)=(dk+1-1)(d-1)-1.

Therefore, in attempting to settle the values of DNvt(d,k), research activities in this problem follow the next two directions:

• Increasing the lower bounds for DNvt(d,k) by constructing ever larger vertex-transitive digraphs.
• Lowering and/or setting upper bounds for DNvt(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 DNvt(d,k)

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 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 open problem.

### Table of the orders of the largest known vertex-symmetric graphs for the directed degree diameter problem

Digraphs in bold are optimal.

 d\k 2 3 4 5 6 7 8 9 10 11 12 2 6 10 20 27 72 144 171 336 504 737 3 12 27 60 165 333 1 152 2 041 5 115 11 568 41 472 4 20 60 168 720 1 378 7 200 14 400 42 309 172 800 1 036 800 1 296 000 5 30 120 360 2 520 5 040 40 320 86 400 362 880 1 814 405 12 700 800 15 552 000 6 42 210 840 6 720 20 160 181 440 362 880 3 628 800 11 289 600 39 916 800 270 950 400 7 56 336 1 680 15 120 60 480 604 800 1 814 400 19 958 400 50 803 200 479 001 600 1 828 915 200 8 72 504 3 024 30 240 151 200 1 663 200 6 692 800 79 833 600 239 500 800 3 113 510 400 9 144 576 000 9 90 720 5 040 55 400 332 640 3 991 680 19 958 400 259 459 200 1 037 836 800 14 329 715 200 43 589 145 600 10 110 990 7 920 95 040 665 280 8 648 640 58 891 840 716 485 750 3 632 428 800 54 486 432 000 217 945 728 000 11 132 1 320 11 880 154 440 1 235 520 17 297 280 121 080 960 1 816 214 400 10 897 286 400 174 356 582 400 871 782 912 000 12 156 1 716 17 160 240 240 2 162 160 32 432 400 259 459 200 4 151 347 200 29 059 430 400 494 010 316 800 2 964 061 900 800 13 182 2 184 24 024 360 360 3 603 600 57 657 600 518 918 400 8 831 612 800 70 572 902 400 1 270 312 243 200 8 892 185 702 400

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

 Color Details * Family of digraphs found by W.H.Kautz. More details are available in a paper by the author. * Family of digraphs found by V.Faber and J.W.Moore. More details are available also by other authors. * Digraph found by V.Faber and J.W.Moore. The complete set of cayley digraphs in that order was found by Eyal Loz. * Digraphs found by Francesc Comellas and M. A. Fiol. More details are available in a paper by the authors. * Cayley digraphs found by Michael J. Dinneen. Details about this graph are available in a paper by the author. * Cayley digraphs found by Michael J. Dinneen. The complete set of cayley digraphs in that order was found by Eyal Loz. * Cayley digraphs found by Paul Hafner. Details about this graph are available in a paper by the author. * Cayley digraph found by Paul Hafner. The complete set of cayley digraphs in that order was found by Eyal Loz. * Digraphs found by J. Gómez. More details are available in two papers by the author. * Cayley digraphs found by Eyal Loz. More details are available in a paper by Eyal Loz and Jozef Širáň.

## Lowering and/or setting upper bounds for DNvt(d,k)

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

## References

• Comellas, F.; Fiol, M.A. (1995), "Vertex-symmetric digraphs with small diameter", Discrete Applied Mathematics 58: 1–12.
• Dinneen, Michael; Hafner, Paul R. (1994), "New Results for the Degree/Diameter Problem", Networks 24 (7): 359–367, PDF version
• 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.
• Gomez, J. (2007), "Large Vertex Symmetric Digraphs", Networks 50 (4): 241–250.
• Gomez, J. (2009), "On large vertex symmetric digraphs", Discrete Mathematics 309 (6) : 1213–1221.
• Kautz, W.H. (1969), "Design of optimal interconnection networks for multiprocessors", Architecture and Design of Digital Computers, Nato Advanced Summer Institute: 249–272.
• Loz, Eyal; Širáň, Jozef (2008), "New record graphs in the degree-diameter problem", Australasian Journal of Combinatorics 41: 63–80.
• Miller, Mirka; Širáň, Jozef (2005), "Moore graphs and beyond: A survey of the degree/diameter problem", Electronic Journal of Combinatorics Dynamic survey D, PDF version