Largest Known (Degree, Diameter)-Graphs

Diameter 2

Last modification: July 18, 1998 23:04 GMT.
http://www-mat.upc.es/grup_de_grafs/desc_g.html

The Petersen Graph
Degree= 3, Diameter = 2; Order =10; Moore bound=10; optimal
Bibliography: Any book on Graph Theory, e.g. F. Comellas, J. Fàbrega, A. Sánchez, O. Serra. Matemática Discreta. Edicions UPC, Universitat Politécnica de Catalunya, 1994, 374 +ix pages, ISBN 84-7653-413-2.
K3*C5
Delta= 4, Diam= 2; N=15; Moore bound=17; optimal.
Download the adjacency list


K3*X8
Delta= 5, Diam= 2; N=24; Moore bound=26;
Download the adjacency list
K4*X8, Wegner(?)
Delta= 6, Diam= 2; N=32; Moore bound=37;
Download the adjacencies list of the graph.
Download comments and the incidence list of the Wegner (?) graph (provided by C. Delorme)
Paul Hafner pointed out (July 1998) that the Wegner graph is isomorphic (with automorphism group of order 1920) to the graph described in:
Lutz Twele, Effiziente Implementierung des Todd-Coxeter Algorithmus im Hinblick auf Grad/Durchmesser-Optimierung von knotentransitiven Graphen , Diplomarbeit Universit"at Oldenburg, 1997
(the graph is also listed in Sampels' PhD thesis). Hafner provided a 'prettier' representation for this group and graph, all generators being involutions, < f > is the centre:
< a,b,c,d,e,f | a^2, b^2, c^2, d^2, e^2, f^2, (a * f)^2, (b * f)^2, (c * f)^2, (d * f)^2, (e * f)^2, a * b * a * b * f, c * b * a * d * e, d * b * a * e * c, e * b * a * c * d, a * c * a * c * f, e * c * a * d * b >
For some more info refer to: M.J.Dinneen, Group-Theoretic Methods for Designing Networks (http://www.cs.auckland.ac.nz/CDMTCS/researchreports/082nznews.pdf).

Guillermo Pineda pointed out (May 8, 2008) the existence of a paper in LNCS v.4123 pp. 853-857 (2006) by S.G. Molodsov ( "Largest Graphs of Diameter 2 and Maximum Degree 6" available at http://www.springerlink.com/content/up282173473l0440/ ) reporting his computer search which has generated all largest diameter 2 degree 6 graphs, resulting in 6 non isomorphic graphs with order 32 (one of them is the Wegner graph).
The following 6 links go to the adjacency lists of these graphs in the NetworkX adjacency list format, see http://networkx.lanl.gov.

G1 with automorphism group of order 6
G2 with automorphism group of order 2
G3 with automorphism group of order 144
G4 with automorphism group of order 64
G5 with automorphism group of order 48
G6 with automorphism group of order 1920

The following 6 links go to the adjacency lists of these graphs.
G1 with automorphism group of order 6
G2 with automorphism group of order 2
G3 with automorphism group of order 144
G4 with automorphism group of order 64
G5 with automorphism group of order 48
G6 with automorphism group of order 1920


Hoffman-Singleton
Degree= 7, Diameter = 2; Order =50; Moore bound=50; Moore graph
 V={(a,i,j); a in Z2 ; i,j in Z5} 
 (a,i,j)  -> {(a,i,j + (1+a)), (a,i,j - (1+a)),(a~, l, j + (-1)^a *i*l)  l=0...4
and 0~=1, 1~=0}
Download the adjacency list
(we thank Bill Mann - wmann@avici.com - for correcting the equation and providing the adjacency list)
57
Degree= 8, Diameter = 2; Order =57; Moore bound=65
8 vertices have degree 7 and 49 degree 8
Download the adjacency list of the graph (thanks to E. Canale).
Exoo_104
Degree= 11, Diameter = 2; Order =104; Moore bound=422.
Download the adjacency list of the graph.
133
Degree= 12, Diameter = 2; Order =133; Moore bound=145.
12 vertices have degree 11 and 121 degree 12
Download the adjacency list of the graph (thanks to E. Canale).
MKMS_162
Degree= 13, Diameter = 2; Order =162; Moore bound=170.
B.D. McKay, M. Miller, J. Siran; A note on large graphs of diameter two and given maximum degree.
183
Degree= 14, Diameter = 2; Order =183; Moore bound=197.
14 vertices have degree 13 and 169 degree 14
Download the adjacency list of the graph (thanks to E. Canale).
Canale_187
Degree= 15, Diameter = 2; Order =187; Moore bound= 226.
Description: Canale added 4 vertices to the graph with diameter 2 and max. degree 14 in a non-computer-generated way. The resulting graph has max. degree 15, min. degree 13 and diameter 2.
Download the adjacency list of the graph.
Exoo_198
Delta= 16, Diam= 2; N=198; Moore bound=257;
Download the adjacency list of the graph.