Largest Known (Degree, Diameter)-Graphs (Description)

Largest Known (Degree, Diameter)-Graphs

Diameter 9

Last modification: October 14, 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: Z_m ⋉_a Z_n, of order m·n. Group operation defined as [x,y] × [u,v] = [(x+u) mod m, (y·a^u+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

Dhar_7832

Degree= 4, Diameter = 9; Order =7832; Moore bound=39365.

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 Z₁₁ ⋉₁₅₃Z₁₇₈, of order 1958. The group operation is defined by [x,y] × [u,v] = [(x+u) mod 11, (y·153^u+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 Z₁₁ (⋊₅₈) Z₃₅₃, 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.

Dhar_59294

Degree= 5, Diameter = 9; Order =59294; Moore bound= 436904.

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 Z₂₃ ⋉₉₁₆Z₁₂₈₉, of order 29647. The group operation is defined by [x,y] × [u,v] = [(x+u) mod 23, (y·916^u+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 Z₄₈ (⋊₂₂) Z₁₂₀₅ 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 Z₄₉ (⋊₄₁) Z₆₇₆₃ (no voltages), generators [25,1254 ]<>[24,2125 ]:[18,541 ]<>[31,3289 ]:[47,4642 ]<>[2,1300 ] and checks its diameter, degree and distance distribution.

Dhar_1227774

Degree= 7, Diameter = 9; Order =1227774; Moore bound= 141087739.

Voltage lift of a base graph with 2 vertices over the metacyclic group Z₅₁ ⋉₈₈₆₀ Z₁₂₀₃₇ of order 613887: the vertices are the pairs (copy, group element) and (c,x) is adjacent to (c',x # g) for each of the 7 units (loop pairs inside a copy, edges between copies) listed in the .json file.

Download this file with a .json file and other details to reconstruct the graph. 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 result, order=1224680

Obtained by Rishabh Rajiv (rishabh.rajiv@alumni.ubc.ca, September 24, 2026) with the use of AI agentic coding systems. The graph is a Cayley graph for a semidirect product.

In this link https://doi.org/10.5281/zenodo.22928337 you can download the edge list, a paper and information detailing the construction of the graph.

Current entries for diameter 9 and degrees 8 to 16 found by (dharyugi@gmail.com; Chalfont, PA, USA; October 6-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. All graphs are voltage lifts of a base graph with 2 vertices over a metacyclic group Z_m ⋉_a Z_n.

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

Former results (up to October 14, 2026)

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