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

Largest Known (Degree, Diameter)-Graphs

Diameter 3

Last modification: September 15, 2026; June 22, 2025, html corrections. April 13, 2025. -- added adjacency lists for entries (9,3), (10,3), (11,3), (12,3), (14,3), (15,3), and (16.3), provided by V. Pelekhaty --

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.

C5xF4

Degree = 3, Diameter = 3; Order=20; Moore bound=22; optimal

B. Elpass. Topological constraints on interconnection-limited logic. 1964 Proceedings of the Fifth Annual Symposium on Switching Circuit Theory and Logical Design, Princeton, NJ, USA, 1964, pp. 133-137. doi:10.1109/SWCT.1964.27

A detailed description: I. Alegre, M.A. Fiol and J.L.A Yebra; Some large graphs with given degree and diameter; J. Graph Theory,10 (1986), pp.219-224. doi:10.1002/jgt.3190100211

Download the NX adjacency list of C5xF4. Download the implicit adjacency list of C5xF4.

This SageMath script computes several properties of the graphs including symmetry group sizes and the number of k-cycles (k=3..10). This is the online version .

Allwr

Degree = 4, Diameter = 3; Order =41; Moore bound=53;

Graphs found by James Allwright (School of Computer Science, University of Westminster) by using a heuristic algorithm.

13 non isomorphic graphs with 41 vertices were found.

J. Allwright, New (Delta, D) graphs discovered by heuristic search. Discrete Applied Mathematics , 37/38 (1992), pp. 3--8.

Adjacency list NX of Graph 1(a).

Adjacency list NX of Graph 1(b). Obtained from 1(a) by the 2-swap [(25,34),(30,33) to (25,33),(30,34)].

Adjacency list NX of Graph 1(c) . Obtained from 1(b) by the 2-swap [(31,6), (32,5) to (31,5), (32,6)].

Adjacency list NX of Graph 1(d) . Obtained from 1(c) by the 2-swap [(17,20), (28,31) to (17,31), (28,20)].

Adjacency list NX of Graph 1(e) . Obtained from 1(d) by the 2-swap [(16,21), (27,32) to (16,32), (27,21)].

Adjacency list NX of Graph 1(f) . Obtained from 1(e) by the 2-swap [(14,33), (19,34) to (14,34), (19,33)].

Adjacency list NX of Graph 2(a) .

Adjacency list NX of Graph 2(b) . Obtained from 2(a) by the 2-swap [(4,35), (7,38) to (4,38), (7,35)].

Adjacency list NX of Graph 2(c) . Obtained from 2(b) by the 2-swap [(16,31), (17,32) to (16,32), (17,31)].

Adjacency list NX of Graph 3 .

Adjacency list NX of Graph 4 .

Adjacency list NX of Graph 5 .

Adjacency list NX of Graph 6 .

Graphs 1(a) to 1(f) all share the same average distance of 2.5036585. Graphs 3, 4, 5 and 6 have an average distance of 2.5.

I corrected Graph 4 from the Fig. 3 of Allwright's paper, as it initially produced a graph with a diameter of 4. If we label the vertices of Graph 4 from Fig. 3 of the paper from left to right and top to bottom (starting with 1), we need to swap the edges (12, 32) and (13, 37) to obtain the intended graph, which gives the correct values for the diameter and the number of k-cycles in the paper. In the above figure, I have removed the wrong edges and added (in red) the correct ones.

This SageMath script computes several properties of the graphs including symmetry group sizes and the number of k-cycles (k=3..10). This is the online version .

Note that a few values computed by this script with respect symmetry group sizes do not match those reported in the paper. I have verified these results with Mathematica and I believe they are correct. Also the value of the number of 9-cycles for Graph 6 is 937 and not 938 as stated in the paper (likely a misprint).

Exoo_72

Degree = 5, Diameter = 3; Order =72; Moore bound=106;

Communicated by G. Exoo (May 22, 1998). G.E. data

Download the implicit adjacency list of the graph.

Download the adjacency list NX of the graph.

Geoffrey Exoo. A family of graphs and the degree/diameter problem. J. Graph Theory 37 (2001), 118-124.

This SageMath script computes several properties of the graphs including symmetry group sizes and the number of k-cycles (k=3..10). This is the online version .

Exoo_111

Degree = 6, Diameter = 3; Order =111; Moore bound=187;

Communicated by G. Exoo (May 19, 2010). G.E. data

Download the implicit adjacency list and the NX adjacency list of the graph.

Note that this graph is vertex-symmetric and edge-symmetric but not Cayley.

This SageMath script computes several properties of the graphs including symmetry group sizes and the number of k-cycles (k=3..10). This is the online version .

Exoo_168

Degree = 7, Diameter = 3; Order =168; Moore bound=302;

Communicated by G. Exoo (November 1, 2005). G.E. data

Download the implicit adjacency list and the NX adjacency list of the Exoo graph.

M. Conder found (2011) an optimal Cayley graph (7,3)=168 (non isomorphic with the Exoo graph, which is not Cayley). Clik here for more details and the edge list (original information from Marston Conder at combinatoricswiki.org).

F. Comellas (May 2026) found four other non-isomorphic Cayley graphs with properties different from those of Conder's graph. They arise from the group SmallGroup(168,43) and are denoted SG168x43x1, SG168x43x2, SG168x43x4, and SG168x43x5. The graphs SG168x43x1 and SG168x43x2 have girth 4 and an automorphism group of order 336, as does Conder's graph. In contrast, SG168x43x4 has girth 3 and an automorphism group of order 168, while SG168x43x5 has girth 5 and also an automorphism group of order 168. The numbers of cycles and the values of the algebraic connectivity are also different.

This SageMath script computes several properties for all these graphs including symmetry group sizes, distance distributions and the number of k-cycles (k=3..10). This is the online version .

CM_253

Degree= 8, Diameter = 3; Order =253; Moore bound=457.

Obtained (08/1994) by F. Comellas, M. Mitjana as a Cayley graph for a semidirect product.

Z_11*(9)Z_23 -- [7,2]<>[4,11]; [10,4]<>[1,10]; [1,16]<>[10,11]; [9,17]<>[2,3]

Snapshot of the web publication (Internet Archive, December 1, 1996 )

Dist. Distrib. 1,8,52,192, avg. dist.: 2.730159 (implicit adjacency list ) --- adjlist NX

Other instances found (F.Comellas 2024) -all are isomorphic to the former-

Z_11*(2)Z_23 -- [5,14]<>[6,1]; [5,11]<>[6,9]; [2,9]<>[9,15]; [10,4]<>[1,15] Avg. dist. 2.730159 adjlist NX

Z_11*(3)Z_23 -- [9,1]<>[2,14]; [4,1]<>[7,21]; [3,12]<>[8,20]; [2,4]<>[9,20] Avg. dist. 2.730159 adjlist NX

Z_11*(4)Z_23 -- [8,9]<>[3,22]; [10,0]<>[1,0]; [5,10]<>[6,3]; [8,14]<>[3,1] Avg. dist. 2.730159 adjlist NX

Z_11*(6)Z_23 -- [1,17]<>[10,1]; [6,5]<>[5,13]; [8,4]<>[3.10]; [3,3]<>[8,15] Avg. dist. 2.730159 adjlist NX

Z_11*(8)Z_23 -- [2,6]<>[9,15]; [2,17]<>[9,8]; [7,14]<>[4,18]; [3,0]<>[8,0] Avg. dist. 2.730159 adjlist NX

Z_11*(12)Z_23 -- [2,0]<>[9,0]; [1,8]<>[10,7]; [5,13]<>[6,21]; [6,2]<>[5,10] Avg. dist. 2.730159 adjlist NX

Z_11*(13)Z_23 -- [4,3]<>[7,19]; [3,3]<>[8,17]; [5,17]<>[6,13]; [7,18]<>[4,21] Avg. dist. 2.730159 adjlist NX

Z_11*(16)Z_23 -- [7,5]<>[4,1]; [3,21]<>[8,1]; [4,3]<>[7,15]; [6,18]<>[5,7] Avg. dist. 2.730159 adjlist NX

Z_11*(18)Z_23 -- [2,16]<>[9,15]; [10,19]<>[1,3]; [10,17]<>[1,16]; [4,1]<>[7,17] Avg. dist. 2.730159 adjlist NX

--------------------

253deg8D3-FC.zip is a zip file containing the programs used to obtain the results for this graph and for the graphs (3,5), (6,8), (7,6), (7,7), (8,5), (9,4), (10,4), (10,5), (11,5), (12,5), (13,5), (14,5), and (15,5), which were found by the author in 2024. The C program included is the same one that computed this particular (8,3) entry in 1994, with only minor modifications to its output format. See entries (3,5)=70 and (3,8)=360 for other versions of these programs.

--------------------

This SageMath script computes several properties of the graphs including symmetry group sizes and the number of k-cycles (k=3..10). This is the online version .

--------------------

Also obtained in January 1997 as a Cayley graph for semidirect product of Zm with Zn.

Z_11*(3)Z_23 -- [2,0]<>[9,0]; [2,13]<>[9,19]; [3,1]<>[8,17]; [4,22]<>[7,2]

avg. dist.: 2.730159

M. Sampels. Large networks with small diameter. Proc. 23rd Int. Workshop on Graph Theoretic Concepts in Computer Science (WG'97), LNCS 1335, pp. 288-302. Springer-Verlag, 1997. Communicated July 29, 1997 adjlist NX.

This instance is also isomorphic to the other cases.

Q′₈

Degree = 9, Diameter = 3; Order =585; Moore bound= 658;

Quotient of the incidence graph of a regular generalized quadrangle by a polarity.

C. Delorme. Grands graphes de degré et diamètre donnés.Eur. J. Comb. 6 (1985), pp. 291-302. link to the paper

Thanks to V. Pelekhaty, you can download the implicit adjacency list and the adjlist NX of the graph.

This SageMath script computes several properties of the graphs including symmetry group sizes and the number of k-cycles (k=3..10). This is the online version .

Q′₈d

Degree = 10, Diameter = 3; Order =650; Moore bound= 911;

Quotient of the incidence graph of a regular generalized quadrangle by a polarity with duplication of some vertices.

C. Delorme. Grands graphes de degré et diamètre donnés.Eur. J. Comb. 6 (1985), pp. 291-302. link to the paper

Thanks to V. Pelekhaty, you can download the implicit adjacency list and the adjlist NX of the graph.

This SageMath script computes several properties of the graphs including symmetry group sizes and the number of k-cycles (k=3..10). This is the online version .

Q′₈d

Degree = 11, Diameter = 3; Order =715; Moore bound= 1222;

Quotient of the incidence graph of a regular generalized quadrangle by a polarity with duplication of some vertices.

C. Delorme. Grands graphes de degré et diamètre donnés.Eur. J. Comb. 6 (1985), pp. 291-302. link to the paper

Thanks to V. Pelekhaty, you can download the implicit adjacency list and the adjlist NX of the graph.

This SageMath script computes several properties of the graphs including symmetry group sizes and the number of k-cycles (k=3..10). This is the online version .

Q′₈d++

Degree = 12, Diameter = 3; Order =791; Moore bound= 1597;

Dharunish Yugeswardeenoo (dharyugi@gmail.com; Sept. 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.

One new vertex is added to the 790-vertex graph (below): 234 of its edges are deleted and 17 new edges are added between its vertices, and the new vertex is joined to 12 original vertices. Degree histogram : [0, 0, 0, 0, 0, 0, 0, 0, 0, 79, 53, 79, 580]

Download the raw 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 .

Former result, order=790

Dharunish Yugeswardeenoo (dharyugi@gmail.com; August 17,2026). Addition of vertices to the graph below. 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 .

Former result, order=786

Q′₈d+, quotient of the incidence graph of a regular generalized quadrangle by a polarity with duplication of some vertices.

J. Gómez. Some new large (Δ,3) graphs.Networks 53 (2009), pp. 1-5. link

Thanks to V. Pelekhaty, you can download the implicit adjacency list and the adjlist NX of the graph.

This SageMath script computes several properties of the graphs including symmetry group sizes and the number of k-cycles (k=3..10). This is the online version .

Q′₈d++

Degree = 13, Diameter = 3; Order =859; Moore bound=2042;

Three new vertices are added to V. Pelekhaty's 856-vertex graph (below): 354 of its edges are deleted and 80 new edges are added between its vertices; each new vertex is joined to 13 original vertices, and the new vertices are not adjacent to each other. Degree histogram: [0, 0, 0, 0, 0, 0, 0, 0, 0, 33, 63, 59, 70, 634]

Download the raw 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 .

Former result, order=856

Obtained by Vladimir Pelekhaty (vpelekhaty@aol.com, August 6, 2021.) "I started with Jose Gomez's Q′₈d+ graph (13,3)=851 --see link -- , and added a few (odd number of) nodes before regularizing it by connecting the dangling degrees".

Download the implicit adjacency list of the graph. adjlist NX

This SageMath script computes several properties of the graphs including symmetry group sizes and the number of k-cycles (k=3..10). This is the online version .

Rajiv_1053

Degree = 14, Diameter = 3; Order =1053; Moore bound= 2563;

Obtained by Rishabh Rajiv (rishabh.rajiv@alumni.ubc.ca, August 24, 2026) with the use of AI agentic coding systems as a Cayley graph for the semidirect product Z₉ (⋊₁₆) Z₁₁₇ with generators [7,102 ]<>[2,96 ]:[8,29 ]<>[1,4 ]:[4,14 ]<>[5,43 ]:[1,33 ]<>[8,93 ]:[8,35 ]<>[1,25 ]:[5,95 ]<>[4,1 ]:[2,73 ]<>[7,2 ]: avg. dist.: 2.79772, dist. distrib. [1, 14, 82, 856]

In this link you can download the adjacency list, the verifier (standard-library Python, no dependencies), and a paper describing the construction 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 1032.

Graph obtained by Mark Marosi (August 17, 2026) Department of Measurement and Information Systems, Budapest University of Technology and Economics (BME), Budapest, Hungary (marosi@mit.bme.hu). Marosi used Claude (Anthropic) for the search -details will come later-. The graph is a Cayley graph for the semidirect product Z₃ (⋊₃₃₇) Z₃₄₄ with generators [1,220 ]<>[2,228 ]:[1,219 ]<>[2,277 ]:[1,105 ]<>[2,15 ]:[1,189 ]<>[2,27 ]:[1,87 ]<>[2,209 ]:[1,43 ]<>[2,301 ]:[1,192 ]<>[2,224 ]. Deg. histogram.: [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1032], avg. dist.: 2.798254

This is the online SageMath script which computes some proerties

Former result, order 979

Obtained by Rishabh Rajiv (rishabh.rajiv@alumni.ubc.ca -communicated July 4, 2026) as a Cayley graph for the semidirect product Z₁₁ (⋊₄₅) Z₈₉ with generators [0,44 ]<>[0,45 ]:[1,43 ]<>[10,3 ]:[1,52 ]<>[10,74 ]:[1,80 ]<>[10,18 ]:[2,8 ]<>[9,57 ]:[4,14 ]<>[7,43 ]:[4,50 ]<>[7,1 ] avg. dist.: 2.785276

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

This SageMath script computes several properties of the graphs including symmetry group sizes and the number of k-cycles (k=3..7). This is the online version .

Former result, order 916

J. Gómez. Some new large (Δ,3) graphs.Networks 53 (2009), pp. 1-5. link

Thanks to V. Pelekhaty, you can download the implicit adjacency list and the adjlist NX of the graph.

This SageMath script computes several properties of the graphs including symmetry group sizes and the number of k-cycles (k=3..10). This is the online version .

Former result, order 912

Geoff Exoo (2001). G.Exoo. A family of graphs and the degree/diameter problem. J. Graph Theory 37 (2001), pp. 118-124. link

Download the adjacency list of the graph.

(⊗ Q_2,4)′+

Degree = 15, Diameter = 3; Order =1224; Moore bound= 3166;

Graph constructed with the help of AI tools by Petrit Isufi (August 13, 2026; isufi.petrit@proton.me). Nine new vertices are added to the 1215-vertex (⊗ Q_2,4)′ Delorme-Farhi graph which remains unchanged. Download the edge list of the graph.

Dharunish Yugeswardeenoo ( August 15, 2026; dharyugi@gmail.com) found independently, also with the help of AI tools, a non-isomorphic graph with the same properties. Download the edge list of this graph.

This SageMath script computes several properties of the graphs including symmetry group sizes and the number of k-cycles (k=3..10). This is the online version .

Former result, order 1215

(⊗ Q_2,4)′ with 1215 vertices. Component with polarity of the cartesian product of the quocient of a quadrangle by a polarity by itself.

C. Delorme. Large bipartite graphs with given degree and diameter. J. Graph Theory, 9 (1985) 325–334.

Thanks to V. Pelekhaty, you can download the implicit adjacency list and the adjlist NX of the graph.

(⊗ Q₃)′+

Degree = 16, Diameter = 3; Order =1610; Moore bound= 3857;

Dharunish Yugeswardeenoo (dharyugi@gmail.com; August 17,2026). Spread-block completion of a product of generalized-quadrangle graphs (see below). 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. xQ3pp Ord.: 1610 / Size: 12880 / Diam.: 3 / Avg.dist: 2.87602 / 16-reg.? True / Girth: 3 / Aut.group.ord.: 1440 / Cayley ? False --- vtx.trans. ? False -- edge.trans. ? False / Automorphism group structure -> xQ24pp: C2 x S6 | center order: 2 / distance distrib from vtx. 0: [1, 16, 153, 1440]

Download the raw adjacency list .

This SageMath script computes several properties of the graphs including symmetry group sizes and the number of k-cycles (k=3..10). This is the online version .

Former result, order 1600

(⊗ Q₃)′ ; with 16005 vertices. Component with polarity of the cartesian product of the quocient of a quadrangle by a polarity by itself.

C. Delorme and G. Farhi. Large graphs with given degree and diameter.IEEE Trans, Comput. c-33 (1984), pp. 857-860. link to the paper

Thanks to V. Pelekhaty, you can download the implicit adjacency list and the adjlist NX of the graph.

This SageMath script computes several properties of the graphs including symmetry group sizes and the number of k-cycles (k=3..10). This is the online version .