Grahame: 1 revision imported

2019-01-03T14:39:33Z

1 revision imported

CW>Gpineda: /* References */

2013-05-21T13:02:29Z

‎References

New page

==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 [http://en.wikipedia.org/wiki/Vertex-transitive_graph 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 [[The Degree/Diameter Problem | degree diameter problem]] for digraphs of [http://en.wikipedia.org/wiki/Outdegree out-degree] at most 3 ≤ ''d'' ≤ 16 and [http://en.wikipedia.org/wiki/Distance_(graph_theory) 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 [http://en.wikipedia.org/wiki/Open_problem open problem].

===Table of the orders of the largest known vertex-symmetric graphs for the directed degree diameter problem===
Digraphs in bold are optimal.

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

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

<center>
{| border="1" cellspacing="1" cellpadding="1" style="text-align: left;"
|'''Color''' || style="text-align: center;" |'''Details'''
|-
|style="background-color: blue; text-align: center;" | * || Family of digraphs found by W.H.Kautz. More details are available in a paper by the author.
|-
|style="background-color: #6666CC; text-align: center;" | * || Family of digraphs found by V.Faber and J.W.Moore. More details are available also by other authors.
|-
|style="background-color: #669999; text-align: center;" | * || Digraph found by V.Faber and J.W.Moore. The complete set of cayley digraphs in that order was found by Eyal Loz.
|-
|style="background-color: #990099; text-align: center;" | * || Digraphs found by Francesc Comellas and M. A. Fiol. More details are available in a paper by the authors.
|-
|style="background-color: #99FF00; text-align: center;" | * || Cayley digraphs found by Michael J. Dinneen. Details about this graph are available in a paper by the author.
|-
|style="background-color: #FF0033; text-align: center;" | * || Cayley digraphs found by Michael J. Dinneen. The complete set of cayley digraphs in that order was found by Eyal Loz.
|-
|style="background-color: #663333; text-align: center;" | * || Cayley digraphs found by Paul Hafner. Details about this graph are available in a paper by the author.
|-
|style="background-color: #666633; text-align: center;" | * || Cayley digraph found by Paul Hafner. The complete set of cayley digraphs in that order was found by Eyal Loz.
|-
|style="background-color: #666666; text-align: center;" | * || Digraphs found by J. Gómez. More details are available in two papers by the author.
|-
|style="background-color: #FF9900; text-align: center;" | * || Cayley digraphs found by Eyal Loz. More details are available in a paper by Eyal Loz and Jozef Širáň.
|}
</center>

==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, [http://arxiv.org/PS_cache/math/pdf/9504/9504214v1.pdf 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, [http://www.combinatorics.org/Surveys/ds14.pdf PDF version]

==External links==
* [http://maite71.upc.es/grup_de_grafs/table_g.html Vertex-symmetric Digraphs] online table.
* [http://www.eyal.com.au/wiki/The_Degree/Diameter_Problem Eyal Loz's] Degree-Diameter problem page.

[[Category:The Degree/Diameter Problem]]

← Older revision	Revision as of 14:39, 3 January 2019
(No difference)

The Degree Diameter Problem for Vertex Symmetric Digraphs - Revision history

Grahame: 1 revision imported

CW>Gpineda: /* References */