Largest Known (Degree, Diameter)-Graphs

Diameter 9

Last modification: October 22, 2026.
https://web.mat.upc.edu/francesc.comellas/old-files/delta-d/table_degree_diameter.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.
semidirect product Follows the notation of the original contributions from Dinneen and Hafner (arXiv preprint) Networks, 24 (1994) 359-367: Zm ⋉a Zn, of order m·n. Group operation defined as [x,y] × [u,v] = [(x+u) mod m, (y·au+v) mod n]].
Exoo_600
Degree= 3, Diameter = 9; Order =600; Moore bound=1534.
Voltage graph.
Download the implicit adjacency list of the graph.
This SageMath script computes several properties of the graphs including symmetry group sizes and the number of k-cycles (k=3..). This is the online version
Bhakar_7884
Degree= 4, Diameter = 9; Order =7884; Moore bound=39365.
Obtained by Nishant Bhakar (nishant.bhakar@gmail.com, Redmond, WA, USA; October 15, 2026), who set the research, selected the topics to pursue, and reviewed the results. Claude Fable assisted with the computational searches, code development, analysis, and summarization of the results.
Graph constructed as a three-copy voltage lift over the semidirect product Z36 ⋉18Z73, of order 2628. The group operation (following the notation of the original contributions to this table -see top of this page-) is defined by [x,y] × [u,v] = [(x+u) mod 36, (y·18u+v) mod 73]. The construction uses three copies of the group, labelled 0, 1, and 2. Copies 0 and 1 are connected by three generators (0,0), (26,50), and (22,7), corresponding to the integers 0, 1948, and 1613, respectively. Copies 0 and 2 are connected by the identity generator (0,0), while copies 1 and 2 are connected by the generator (30,8), corresponding to the integer 2198. Copy 2 has an internal inverse-pair generator (33,0), corresponding to the integer 2409. Each connecting generator also defines its inverse edge in the opposite direction. The resulting graph has 3·2628 = 7884 vertices, is 4-regular, and has diameter 9.
In this link you can download the edge list and more information detailing the construction of the graph.
Download the local edge list of the graph.
This SageMath script computes several properties of the graphs. This is the online version .

Former result, order=7832
Dharunish Yugeswardeenoo (dharyugi@gmail.com; Chalfont, PA, USA; October 7, 2026). Results obtained by using a hybrid discovery framework in development: LLM-guided search over classical algebraic constructions, combined with local search and exact completion. The specific LLMs used were OpenAI's Sol 5.6 and Anthropic's Claude Fable 5 Max.
A graph with maximum degree 4, diameter 9, and 7832 vertices is constructed as a four-copy voltage lift over the semidirect product Z11 ⋉153Z178, of order 1958. The group operation is defined by [x,y] × [u,v] = [(x+u) mod 11, (y·153u+v) mod 178]. The construction uses four copies of the group, with inverse-pair generators [4,140], [5,144], [9,167], and [7,143] in copies 0, 1, 2, and 3, respectively. The copies are connected by four voltage edges: 0–2 with generator [5,65], 0–3 with generator [3,149], 1–2 with generator [7,65], and 1–3 with generator [0,150]. Each voltage edge also includes its inverse in the opposite direction. The resulting graph has 4·1958 = 7832 vertices. .
Download the local edge list of the graph.
This SageMath script computes several properties of the graphs including symmetry group sizes and the number of k-cycles (k=3..). This is the online version .

Former result, order=7766
Dharunish Yugeswardeenoo (dharyugi@gmail.com; Chalfont, PA, USA; August 31,2026). Voltage lift of a 2-vertex base (loop at each vertex, two parallel links) over the semidirect product Z11 (⋊58) Z353, voltages [(10, 235), (5, 218), (0, 0), (3, 349)]. Results obtained by using a hybrid discovery framework in development: LLM-guided search over classical algebraic constructions, combined with local search and exact completion. The specific LLMs used were OpenAI's Sol 5.6 and Anthropic's Claude Fable 5 Max. Download the raw adjacency list .
This SageMath script computes several properties of the graphs. This is the online version .

Former result, Order = 7575
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.
Bhakar_60686
Degree= 5, Diameter = 9; Order =60686; Moore bound= 436906.
Obtained by Nishant Bhakar (nishant.bhakar@gmail.com, Redmond, WA, USA; October 15, 2026), who set the research, selected the topics to pursue, and reviewed the results. Claude Fable assisted with the computational searches, code development, analysis, and summarization of the results.
Graph constructed as a two-copy voltage lift over the semidirect product Z19 ⋉3Z1597, of order 30343. The group operation (following the notation of the original contributions to this table -see top of this page-) is defined by [x,y] × [u,v] = [(x+u) mod 19, (y·3u+v) mod 1597]. The construction uses two copies of the group, labelled 0 and 1, with internal inverse-pair generators (17,0) and (15,1260), respectively, corresponding to the integers 27149 and 25215. The copies are connected by three generators: (0,0), (16,1183), and (10,686), corresponding to the integers 0, 26735, and 16656, respectively. Each connecting generator also defines its inverse edge in the opposite direction. The resulting graph has 2·30343 = 60686 vertices, is 5-regular, and has diameter 9.
In this link you can download the edge list and more information detailing the construction of the graph.

Former result, order=59294
Dharunish Yugeswardeenoo (dharyugi@gmail.com; Chalfont, PA, USA; October 14, 2026). Results obtained by using a hybrid discovery framework in development: LLM-guided search over classical algebraic constructions, combined with local search and exact completion. The specific LLMs used were OpenAI's Sol 5.6 and Anthropic's Claude Fable 5 Max.
A graph constructed as a two-copy voltage lift over the semidirect product Z23 ⋉916Z1289, of order 29647. The group operation is defined by [x,y] × [u,v] = [(x+u) mod 23, (y·916u+v) mod 1289]. The construction uses two copies of the group, with inverse-pair generators [9,395] and [11,8] for the first and second copies, respectively, corresponding to the integers 11996 and 14187. The copies are connected by three generators [12,141], [20,649], and [5,1123], corresponding to the integers 15609, 26429, and 7568. Each connecting generator also defines an inverse edge in the opposite direction. The resulting graph has 2·29647 = 59294 vertices.
Download the local raw adjacency list of the graph.

Former result, order=57840
Communicated by Eyal Loz, Math Dep., Auckland Univ., New Zealand (July 2006)
Obtained as a Cayley graph for the semidirect product Z48 (⋊22) Z1205 with generators [(24,1165)|(41,491)(15,849)]
Link to Eyal Loz's data. (eloz002 @ math .auckland. ac. nz ) Communicated July 2006.
Rod_331387
Degree= 6, Diameter = 9; Order =331 387; Moore bound=2 929 686
nodes: 331387 edges: 994161 min deg: 6 max deg: 6 diameter: 9 avg. dist: 7.758922
Cayley graph.Communicated by Alexis Rodriguez-Eduardo Canale. Instituto de Matematica y Estadistica / Facultad de Ingenieria - UDeLaR / Universidad de la Republica / Uruguay (August 20 2012)
El grafo con 331387 nodos con diámetro 9 y grado 6, los parámetros del grupo fueron: m = 6763, n = 49 y r = 41. El cociente es B(0, 3) con los voltajes: (1254, 25), (541, 18) y (4642, 47)
Rodríguez de los Santos, A. (2013.). B&uacaute;quedas masivas de grafos de gran orden con grado y diámetro acotados. Tesis de maestrí­a. Universidad de la Rep&uacaute;blica (Uruguay). Facultad de Ingeniera.
Download the implicit adjacency list of the graph (13.6 MB).
This C program generates the graph as the semidirect product Z49 (⋊41) Z6763 (no voltages), generators [25,1254 ]<>[24,2125 ]:[18,541 ]<>[31,3289 ]:[47,4642 ]<>[2,1300 ] and checks its diameter, degree and distance distribution.
Current entries for diameter 9 and degrees 7, 10 and 13 found by (dharyugi@gmail.com; Chalfont, PA, USA; October 19, 2026). Results obtained by using a hybrid discovery framework in development: LLM-guided search over classical algebraic constructions, combined with local search and exact completion. The specific LLMs used were OpenAI's Sol 5.6 and Anthropic's Claude Fable 5 Max. The graphs are Cayley graphs of metacyclic groups arising from semidirect products of cyclic groups.
Download this file with a .json file and other details to reconstruct the graphs. Note that, in these files, the AI used the opposite convention for the group operation in the semidirect product compared to the one preferred in this table, which follows the original contributions of M. J. Dinneen and P. Hafner (see the top of this page).

Current entries for diameter 9 and degrees 8 to 16, except 10 and 12, obtained by Nishant Bhakar (nishant.bhakar@gmail.com, Redmond, WA, USA; October 15, 2026), who set the research, selected the topics to pursue, and reviewed the results. Claude Fable assisted with the computational searches, code development, analysis, and summarization of the results. All are Cayley graph constructed over semidirect products.
In this link you can download more information detailing the construction of the graphs. Note that, in these files, the AI used the opposite convention for the group operation in the semidirect product compared to the one preferred in this table, which follows the original contributions of M. J. Dinneen and P. Hafner (see the top of this page).

Former results (up to October 14, 2026)
Entries for diameter 9 and degrees 8 to 16 found by (dharyugi@gmail.com; Chalfont, PA, USA; October 6-14, 2026). See above
Entries for diameter 9 and degrees 10, 12, 14 and 16 obtained by Dharunish Yugeswardeenoo (dharyugi@gmail.com; August 2026).
Result for diameter 9 and degree 13 found by Chenxudong, Hangzhou, China (qq475519905@gmail.com; September 2026). Results for diameter 9 and degrees 8, 9, 11 and 15 obtained by Eyal Loz and Jozef Širáň. New record graphs in the degree-diameter problem. Australas. J. Combin. 41 (2008), 63–80. .