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

Largest Known (Degree, Diameter)-Graphs

Diameter 8

Last modification: September 25, 2026.

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

Degree = 3, Diameter = 8; Order =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.

Download a SageMath script to check several properties of the graph. This is an online version.

Link to Eyal Loz's data. (eloz002 @ math .auckland. ac. nz ) Communicated July 2006.

Dahr_17724

Degree= 5, Diameter = 8; Order =17724; Moore bound=109226

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 5, diameter 8, and 17724 vertices is constructed as a two-copy voltage lift over the semidirect product Z₂₁ ⋉₃₉₁Z₄₂₂, of order 8862. The group operation is defined by [x,y] × [u,v] =[(x+u) mod 21, (y·391^u+v) mod 422]. The construction uses two copies of the group, with inverse-pair generators [10,209] and [16,158] for the first and second copies, respectively, and three generators [0,45], [15,29], and [1,392] connecting the two copies. Each connecting generator also defines an inverse edge in the opposite direction. The resulting graph has 2·8862 = 17724 vertices.

Download the compressed 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 = 17602

Dharunish Yugeswardeenoo (dharyugi@gmail.com; August 17, 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. Voltage lift of a 3-vertex base multigraph over the semidirect group Z_677 (x362) Z_13. Order: 17602 / Size: 44005 / 5-reg.? True / Girth: 9 / Diam.: 8 / Avg.dist: 6.70661 / Aut.group.ord.: 8801 / Cayley ? False --- vtx.trans. ? False -- edge.trans. ? False / Automorphism group structure / C677 x| C13

This SageMath online script computes several properties of the graph including symmetry group sizes (run it locally).

Download the raw adjacency list .

Former result, order =17030

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.

Rajiv_78561

Degree= 6, Diameter =8; Order = 78561; Moore bound = 585937.

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 Z₂₁ (⋊₃₁₀) Z₃₇₄₁, S= {4456,15631,23596,56924,65366,78257}

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.

Download the local implicit adjacency list of the graph.

Former result, order = 77343.

Obtained by Rishabh Rajiv (rishabh.rajiv@alumni.ubc.ca, August 24, 2026) with the use of AI agentic coding systems.

Cayley graph of the semidirect group Z₂₁ (⋊₁₀₁₁) Z₃₆₈₃, with generators [16,2082 ]<>[5,294 ]:[14,2934 ]<>[7,3562 ]:[4,2556 ]<>[17,662 ]. Avg.dist: 6.8410586 . Dist. distrib. :[ 1, 6, 30, 150, 750, 3702, 16540, 41470, 14694 ] .

In this link you can download the adjacency list, a verifier (standard-library Python), and a paper describing the construction of the graph.

Former result, order=77257.

Download the raw adjacency list .

Former result, order =76891

Cayley graph. Found as a semidirect product, 76891 nodes and 230673 edges (F.Comellas 2024):

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

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

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

Rajiv_254268

Degree= 7, Diameter =8; Order =254268; Moore bound = 2351462 .

Obtained by Rishabh Rajiv (rishabh.rajiv@alumni.ubc.ca, August 24, 2026) with the use of AI agentic coding systems.

Cayley graph of the semidirect group Z₈₄ (⋊₃₄₁) Z₃₀₂₇, with generators [1,1326 ]<>[83,1878 ]:[39,1977 ]<>[45,2373 ]:[45,2373 ]<>[39,1977 ]:[83,1878 ]<>[1,1326 ]. Avg.dist: 6.933853. Dist. distrib.: [ 1, 7, 42, 252, 1500, 8841, 47085, 142825, 53715 ] .

In this link you can download the adjacency list, a verifier (standard-library Python), and a paper describing the construction of the graph.

Rajiv_ 744878

Degree= 8, Diameter =8; Order = 744878; Moore bound = 7686400 .

Obtained by Rishabh Rajiv (rishabh.rajiv@alumni.ubc.ca, September 30, 2026) with the use of AI agentic coding systems Anthropic's Claude Fable 5.1 and Opus 5.5. Cayley graph for the semidirect product Z₂₃ (⋊₂₄₉₁) Z₃₂₃₈₆ S= {69812, 184915, 266362, 294870, 479750, 502200, 605493, 682624}

In this link: https://doi.org/10.5281/zenodo.23057003 you can download the details and a paper describing the construction of the graph.

Former result, order = 735175.

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.

Former result, order = 735105.

Obtained by Rishabh Rajiv (rishabh.rajiv@alumni.ubc.ca, August 24, 2026) with the use of AI agentic coding systems.

Cayley graph of the semidirect group Z₃₅ (⋊₂₆₈) Z₂₁₀₀₃, with generators [1,19391 ]<>[34,7216 ]:[11,8628 ]<>[24,3102 ]:[20,696 ]<>[15,17478 ]:[28,18332 ]<>[7,16117 ]. Avg.dist: 7.00499928 . Dist. distrib. :[ 1, 8, 56, 392, 2726, 18772, 118058, 425734, 169358] .

In this link you can download the adjacency list, a verifier (standard-library Python), and a paper describing the construction of the graph.

Rajiv_1857060

Degree= 9, Diameter = 8; Order =1857060; Moore bound=2 929 686

Obtained by Rishabh Rajiv (rishabh.rajiv@alumni.ubc.ca, September 30, 2026) with the use of AI agentic coding systems Anthropic's Claude Fable 5.1 and Opus 5.5. Cayley graph for the semidirect product Z₉₀ (⋊₂₃₃) Z₂₀₆₃₄ S= {232439, 393476, 675380, 870223, 938353, 1008533, 1211224, 1472366, 1633979}.

In this link: https://doi.org/10.5281/zenodo.23057003 you can download the details and a paper describing the construction of the graph.

Former result, order = 1698630.

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.

Former result, order = 1697688.

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.

Rajiv_387740

Degree= 10, Diameter = 8; Order =4387740; Moore bound=538084007.

Obtained by Rishabh Rajiv (rishabh.rajiv@alumni.ubc.ca, September 30, 2026) with the use of AI agentic coding systems Anthropic's Claude Fable 5.1 and Opus 5.5. Cayley graph for the semidirect product Z₈₄ (⋊₃₇) Z₅₂₂₃₅ S= {620896, 860419, 1226861, 1565380, 1986157, 2428307, 2888370, 3188413, 3601696, 3858743}

In this link: https://doi.org/10.5281/zenodo.23057003 you can download the details and a paper describing the construction of the graph.

Former result, order = 4293452.

Communicated by Eyal Loz, Math Dep., Auckland Univ., New Zealand (July 2006)

Cayley graph of the semidirect group Z₆₈ (⋊₁₃₇₈) Z₆₃₁₃₉, with generators 40,7668 ]<>[28,61465 ]:[5,16311 ]<>[63,51074 ]:[20,15555 ]<>[48,29103 ]:[52,7399 ]<>[16,23885 ]:[21,22796 ]<>[47,26610 ]: Average distance : 7.08645, Distance distribution: [ 1 , 10, 90, 810, 7290, 65148, 543291, 2606352, 1070460]

Link to Eyal Loz's data. (eloz002 @ math .auckland. ac. nz )

E. Loz, J. Širáň. New record graphs in the degree-diameter problem. Australas. J. Combin. 41 (2008), 63–80.

Rajiv_9260784

Degree= 11, Diameter = 8; Order =9260784; Moore bound=1222222216 .

Obtained by Rishabh Rajiv (rishabh.rajiv@alumni.ubc.ca, September 30, 2026) with the use of AI agentic coding systems Anthropic's Claude Fable 5.1 and Opus 5.5. Cayley graph for the semidirect product Z₄₈ (⋊₄₈₈) Z₁₉₂₉₃₃ S= {770788, 1672954, 1984422, 2160410, 2925207, 4707729, 6502959, 7212950, 7411398, 7764836, 8835553}

In this link: https://doi.org/10.5281/zenodo.23057003 you can download the details and a paper describing the construction of the graph.

Former result, order = 8225902.

Chenxudong (Hangzhou, China; qq475519905@gmail.com; September 28, 2026).

Cayley graph of the semidirect group Z₄₇₈ (⋊₈₁₀₃) Z₁₇₂₀₉, with generators [6,13246 ]<>[472,15454 ]:[165,1539 ]<>[313,3877 ]:[273,4559 ]<>[205,11762 ]:[66,3589 ]<>[412,3261 ]:[413,9502 ]<>[65,1117 ]:[239,12035 ]<>[239,12035 ] Average distance : 7.08902671, Distance distribution: [ 1 , 11, 110, 1100, 10964, 108138, 994955, 5129152, 1981471]

Former result, order = 7442328

Link to Eyal Loz's data. (eloz002 @ math .auckland. ac. nz )

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 12 and 14 found by Dharunish Yugeswardeenoo (dharyugi@gmail.com; August 2026). Results for diameter 7 and degree 13 obtained by Rishabh Rajiv (rishabh.rajiv@alumni.ubc.ca, September 30, 2026). In this link: https://doi.org/10.5281/zenodo.23057003 you can download the details and a paper describing the construction of the graphs.

Results for diameter 8 and degree 15 found by Chenxudong, Hangzhou, China (qq475519905@gmail.com; September 2026).. Result for diameter 8 and degree 16 obtained by Eyal Loz and Jozef Širáň. Details at New record graphs in the degree-diameter problem. Australas. J. Combin. 41 (2008), 63--80.