Top Qs
Timeline
Chat
Perspective
Table of vertex-symmetric digraphs
From Wikipedia, the free encyclopedia
Remove ads
The best known vertex transitive digraphs (as of October 2008) in the directed Degree diameter problem are tabulated below.
Table of the orders of the largest known vertex-symmetric graphs for the directed degree diameter problem
Summarize
Perspective
The footnotes in the table indicate the origin of the digraph that achieves the given number of vertices:
- Family of digraphs found by Kautz (1969).
- Cayley digraphs found by Michael J. Dinneen. Details about these graphs 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 these graphs are available in a paper by the author.
- Family of digraphs found by Faber & Moore (1988).
- Digraph found by Faber & Moore (1988). The complete set of Cayley digraphs in that order was found by Eyal Loz.
- Cayley digraph found by Paul Hafner. The complete set of Cayley digraphs in that order was found by Eyal Loz.
- Digraphs found by Comellas & Fiol (1995).
- Cayley digraphs found by Eyal Loz. More details are available in Loz & Širáň (2008).
- Digraphs found by J. Gómez.
Remove ads
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, arXiv:math/9504214, doi:10.1002/net.3230240702
- Comellas, F.; Fiol, M.A. (1995), "Vertex-symmetric digraphs with small diameter", Discrete Applied Mathematics, 58 (1): 1–12, doi:10.1016/0166-218X(93)E0145-O
- Miller, Mirka; Širáň, Jozef (2005), "Moore graphs and beyond: A survey of the degree/diameter problem" (PDF), Electronic Journal of Combinatorics, Dynamic, survey D
- Loz, Eyal; Širáň, Jozef (2008), "New record graphs in the degree-diameter problem" (PDF), Australasian Journal of Combinatorics, 41: 63–80
Remove ads
External links
- Vertex-symmetric Digraphs online table.
- The Degree - Diameter Problem on CombinatoricsWiki.org.
- Eyal Loz's Degree-Diameter problem page.
Wikiwand - on
Seamless Wikipedia browsing. On steroids.
Remove ads