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

Largest Known (Degree, Diameter)-Graphs

Diameter 9

Last modification: June 22, 2025.

http://www-mat.upc.es/grup_de_grafs/desc_g9.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.

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_7766

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

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.

Loz_57840

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

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

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 diametro 9 y grado 6, los parametros 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úsquedas masivas de grafos de gran orden con grado y diámetro acotados. Tesis de maestría. Universidad de la Repú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.

Results for diameter 9 and degrees 7, 8, 9, 11, 13 and 15 obtained by Eyal Loz and Jozef Širáň. New record graphs in the degree-diameter problem. Australas. J. Combin. 41 (2008), 63–80.

. Entries for diameter 9 and degrees 10, 12, 14 and 16 obtained by Dharunish Yugeswardeenoo (dharyugi@gmail.com; August 2026).