## 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
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.