Largest Known (Degree, Diameter)-Graphs

Diameter 8

Last modification: June 22, 2025.
https://web.mat.upc.edu/francesc.comellas/old-files/delta-d/taula_delta_d.html
raw adjacency list format: the first vertex of each row is adjacent to all the other vertices in that row.
implicit adjacency list format: each row corresponds to a vertex (row 1, vertex 0; row 2, vertex 1; and so on) and contains all vertices adjacent to it.
adjacency list NX NetworkX format. NetworkX format.
Chen_360
Delta= 3, Diam= 8; N=360; Moore bound=766;
Graph found by Jianxiang Chen (2018-10-16)
The graph is derived from the symmetric graph on 144 vertices with diameter 7 and girth 8 by a complete pairing of its edges that has a large symmetric group. Let G be the symmetric graph and ~ the pairing relation on its edges. The graph is constructed as follows: The vertex set of the new graph H is V(G)∪E(G). If v∈V(G), u∈V(G), then they are not connected in H. If v∈V(G), u∈E(G), then they are connected in H iff v∈u in G. If v∈E(G), u∈E(G), then they are connected in H iff v~u by the pairing relation. The graph H is not a Cayley graph. It has 3 vertex orbits.
Download the raw adjacency list of the graph.
Download the adjacency list (NetworkX) of the graph.
Download a SageMath program to generate the graph in sparse6 format. This SGM program online .
Download a Python program to check the graph. Can be easily adapted to check graphs in all other formats on this website. This Python program online
Download a SageMath script to check several properties of the graph. This is an online version.
Loz_3243
Degree= 4, Diameter = 8; Order =3 243; Moore bound=13121.
Communicated by Eyal Loz, Math Dep., Auckland Univ., New Zealand (July 2006)
Download the raw adjacency list of the graph.
Link to Eyal Loz's data. (eloz002 @ math .auckland. ac. nz ) Communicated July 2006.
Loz_17030
Degree= 5, Diameter = 8; Order =16956; Moore bound=109226
Communicated by Eyal Loz, Math Dep., Auckland Univ., New Zealand (July 2006)
Download the raw adjacency list of the graph.
Link to Eyal Loz's data. (eloz002 @ math .auckland. ac. nz ) Communicated July 2006.
Com_76891
Degree= 6, Diameter =8; Order = 76891; Moore bound = 585936.
Cayley graph. Found as a semidirect product, 76891 nodes and 230673 edges (F.Comellas 2024):
  1. Z_17 x(891) Z_4523 generators [6,1326]<>[11,4282]:[4,1336]<>[13,119]:[14,1686]<>[3,3044].
    Degree Distribution: [0, 0, 0, 0, 0, 0, 76891] Avg. dist.: 6.843725 (1,6,30,150,750,3710,16424,40956,14864) transm.: 526214 adjlist NX
  2. Z_17 x(1015) Z_4523 generators [16,343]<>[1,126]:[10,615]<>[7,4094]:[12,3868]<>[5,3995].
    Degree Distribution: [0, 0, 0, 0, 0, 0, 76891] Avg. dist.: 6.843725 (1,6,30,150,750,3710,16424,40956,14864) transm.: 526214 adjlist NX
  3. Z_17 x(4359) Z_4523 generators [14,3786]<>[3,4338]:[12,587]<>[5,1066]:[13,572]<>[4,3253].
    Degree Distribution: [0, 0, 0, 0, 0, 0, 76891] Avg. dist.: 6.838314 (1,6,30,150,750,3720,16408,41374,14452) transm.: 525798 adjlist NX
Graphs 1 and 2 are isomorphic and have a higher transmission (and thus average distance) than graph 3.

Former result, Order = 76461
Communicated by Eyal Loz, Math Dep., Auckland Univ., New Zealand (July 2006)
Voltage graph Z_33 x(79) Z_2317, B(0,3), voltages [(40,5722)(12,5970)(44,3528)]
Z_m x(a) Z_n represents a semidirect product of cyclic groups [x,y][u,v]= [x + u mod m, y*a^u + v mod n].
::: Link to Eyal Loz's original data.
E. Loz, J. Širáň. New record graphs in the degree-diameter problem. Australas. J. Combin. 41 (2008), 63–80.
Results for diameter 8 and degrees 7 to 8 obtained by Eyal Loz and Jozef Širáň. New record graphs in the degree-diameter problem. Australas. J. Combin. 41 (2008), 63–80.
Rod_1697688
Degree= 9, Diameter = 8; Order =1 697 688 ; Moore bound=2 929 686
Communicated by A. Rodríguez de los Santos, November 16, 2012.
Voltage graph Z_72 x(1413) Z_23579, B(1,4), voltages [(8,5958)|(27,6086)|(37,22093)|(33,22621)|(36,2717], avg. dist.: 7.002767,(1,9,72,576,4608,36503,263761,1034151,358007), transm.: 11888507
Z_m x(a) Z_n represents a semidirect product of cyclic groups [x,y][u,v]= [x + u mod m, y*a^u + v mod n].
A. Rodríguez de los Santos, Búsquedas masivas de grafos de gran orden con grado y diámetro acotados. Tesis de maestría (2013). Universidad de la República (Uruguay). Facultad de Ingeniera.
Download the implicit adjacency list (zipped) of the graph (53.3 MB).
This C program generates the graph as the semidirect product Z_72 x(1413) Z_23579 (no voltages) and checks its diameter and vertex degree.
Results for diameter 8 and degrees 10 to 16 obtained by Eyal Loz and Jozef Širáň. New record graphs in the degree-diameter problem. Australas. J. Combin. 41 (2008), 63–80.