The Degree Diameter Problem for Vertex Symmetric Digraphs

From Combinatorics Wiki

Jump to: navigation, search

Contents

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
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 465 1 378 7 200 14 400 42 309 137 370 648 000
5 30 120 360 1 152 3 775 28 800 86 400 259 200 1 010 658 5 184 000
6 42 210 840 2 520 9 020 88 200 352 800 1 411 200 5 184 000 27 783 000
7 56 336 1 680 6 720 20 160 225 792 1 128 960 5 644 800 27 783 000 113 799 168
8 72 504 3 024 15 120 60 480 508 032 3 048 192 18 289 152 113 799 168 457 228 800
9 90 720 5 040 30 240 151 200 1 036 800 7 257 600 50 803 200 384 072 192 1 828 915 200
10 110 990 7 920 55 400 332 640 1 960 200 15 681 600 125 452 800 1 119 744 000 6 138 320 000
11 132 1 320 11 880 95 040 665 280 3 991 680 31 152 000 282 268 800 2 910 897 000 18 065 203 200
12 156 1 716 17 160 154 440 1 235 520 8 648 640 58 893 120 588 931 200 6 899 904 000 47 703 427 200
13 182 2 184 24 024 240 240 2 162 160 17 297 280 121 080 960 1 154 305 152 15 159 089 098 115 430 515 200


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.
* 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

  • Kautz, W.H. (1969), "Design of optimal interconnection networks for multiprocessors", Architecture and Design of Digital Computers, Nato Advanced Summer Institute: 249–272
  • 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
  • J. Dinneen, Michael; Hafner, Paul R. (1994), "New Results for the Degree/Diameter Problem", Networks 24 (7): 359–367, PDF version
  • Comellas, F.; Fiol, M.A. (1995), "Vertex-symmetric digraphs with small diameter", Discrete Applied Mathematics 58: 1–12
  • 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
  • Loz, Eyal; Širáň, Jozef (2008), "New record graphs in the degree-diameter problem", Australasian Journal of Combinatorics 41: 63–80

External links

Retrieved from "http://combinatoricswiki.org/wiki/The_Degree_Diameter_Problem_for_Vertex_Symmetric_Digraphs"