The Degree Diameter Problem for Vertex Symmetric Digraphs
From Combinatorics Wiki
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 DN^{vt}(d,k) of vertices in a vertex-transitive digraph of maximum out-degree d and diameter k.
There are no better upper bounds for DN^{vt}(d,k) than the very general directed Moore bounds DM(d,k)=(d^{k+1}-1)(d-1)^{-1}.
Therefore, in attempting to settle the values of DN^{vt}(d,k), research activities in this problem follow the next two directions:
- Increasing the lower bounds for DN^{vt}(d,k) by constructing ever larger vertex-transitive digraphs.
- Lowering and/or setting upper bounds for DN^{vt}(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 DN^{vt}(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 DN^{vt}(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
- Vertex-symmetric Digraphs online table.
- Eyal Loz's Degree-Diameter problem page.