Largest Known (Degree, Diameter)-Graphs

Diameter 3

last modification: November 1, 2005.
http://www-mat.upc.es/grup_de_grafs/desc_g.html

C5 x F4
Degree= 3, Diam= 3; N=20; Moore bound=22; optimal
A description in: Alegre, I.; Fiol, M.A. and Yebra, J.L.A; Some large graphs with given degree and diameter; J. Graph Theory,10 (1986), pp.219-224
Download a Cabri text file of C5xF4.
Allwr
Delta= 4, Diam= 3; N=41; Moore bound=53;
Graphs found by James Allwright (School of Computer Science, University of Westminster) by using a heuristic algorithm. 13 different graphs with 41 vertices were found
J. Allwright, New (Delta, D) graphs discovered by heuristic search. Discrete Applied Mathematics , 37/38 (1992), pp. 3--8.
Download a adjacecy list of Allwr
Exoo_72
Delta= 5, Diam= 3; N=72; Moore bound=106;
Download the Cabri text file of the graph.
Download the adjacency list of the graph.
Exoo_111
Delta= 6, Diam= 3; N=111; Moore bound=187;
Download the adjacency list of the graph.
Exoo_168
Delta= 7, Diam= 3; N=168; Moore bound=302;
Download the adjacency list of the graph.
CM_253
Degree= 8, Diameter = 3; Order =253; Moore bound=457.
Obtained (June 1994) as a Cayley graph for semidirect product of Zm with Zn.
Group Generators Inverses Order of Generator
11*(9)23 [7 2] [4 11]
[10 4] [1 10]
[1 16] [10 11]
[9 17] [2 3]
Comellas, F.; Mitjana M. In preparation (1995).
Download the adjacency list of the graph.
--------------------
Also obtained in January 1997 as a Cayley graph for semidirect product of Zm with Zn.
11*(3)23 4,0 7,0 3,9 8,15 2,10 9, 2,15 9,6
M. Sampels (Sampels@Informatik.Uni-Oldenburg.DE). Large networks with small diameter. (In preparation)