The Degree Diameter Problem for Vertex Symmetric Digraphs

From Combinatorics Wiki

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

External links

Retrieved from ‘http://combinatoricswiki.org/index.php?title=The_Degree_Diameter_Problem_for_Vertex_Symmetric_Digraphs&oldid=313’