Largest Known (Degree, Diameter)-Graphs
Diameter 4
Last modification: August 28, 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.
Doty, vC, AFY
Degree = 3, Diameter = 4; Order =38; Moore bound=46; optimal
Alegre, Fiol, Yebra, von Conta graph ------- Doty graph
Described independently in:
- [Do82] K.W. Doty; Large regular interconnection networks;
Proc. 3rd. Int. Conf. on Distributed Computing Systems, IEEE Press, Miami, October 1982, pp. 312-317.
link to the paper (local)
- [vCo83] C. von Conta.
Torus and other networks as communication networks with up to some hundred points.
IEEE Trans Comp,c-32 (1983), pp. 657-666.
- [AlFiYe86] 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.
The proof of optimality appeared in:
Dominique Buset.
Maximal cubic graphs with diameter 4. Discrete Appl. Math.101 (2000) pp. 53--61.
The graph constructed by K.W. Doty is not isomorphic to the other graphs (which are)
Download the adjacency list of the graph AFY in NetworkX format (vertices notation as in AlFiYe86).
Download the adjacency list of the graph AFY in NetworkX format (vertices labeled 0,2,...37). This graph has average distance 3.10811. Automorphism group size: 8.
More information at The House of Graphs.
Download the adjacency list of the Doty graph in NetworkX format (vertices labeled 0,2,...37). This graph has average distance 3.11664. Automorphism group size: 16.
More information at The House of Graphs.
--------------------
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 .
Bhakar_104
Degree = 4, Diameter = 4; Order =104; Moore bound=161;
Nishant Bhakar (nishant.bhakar@gmail.com, Redmond, WA, USA; August 27, 2026) found two non-isomorphic graphs with 104 vertices and 208 edges. The construction is a Z_8-voltage graph lift of a 13-vertex base multigraph with loops and semi-edges, followed by a symmetry-breaking repair obtained through iterative experimentation with different approaches, with Claude Fable assisting with implementation and the analysis and summarization of the results..
** Download the 104_d4D4.txt edge list of the graph.
** Download the 104b_d4D4.txt edge list of the non-isomorphic graph.
This SageMath script computes several properties of the graph. This is the online version .
Former result, order 100
Graph constructed by Gavin Uberti (gavin.uberti@gmail.com>; August 22, 2026).
It was found as part of his work; 4-regular graphs are useful in semiconductors because that is the maximum number of x16 PHYs that can be placed horizontally on the bottom of a standard 26x33mm reticle.
Download the edge list of the graph.
This SageMath script computes several properties of the graph. This is the online version .
Former result, order 98
Communicated by G. Exoo (May 19, 2010).
G.E. data
Download the implicit adjacency list of the graph.
adjlist NX format
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
Exoo-212
Degree = 5, Diameter= 4; Order=212; Moore bound=426;
Communicated by G. Exoo (May 21, 2010).
G.E. data
Download the implicit adjacency list of the graph.
adjlist NX format
This SageMath script computes several properties of the graph, including symmetry group sizes and the number of k-cycles (k=3..). This is the online version
Loz_390
Degree= 6, Diameter = 4; Order =390; Moore
bound=937
Communicated by Eyal Loz, Math Dep., Auckland Univ., New Zealand (July 2006)
Voltage graph Z_15 x(3) Z_13, D(2,2), voltages [(2,8)<>(14,4),(0,0)<>(13,6),(9,4)<>(7,7)], avg. dist.: 3.444730
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].
Download the raw adjacency list of the graph.
adjlist NX format
Link to Eyal Loz's data (internet archive) .
This SageMath script computes several properties of the graph, including symmetry group sizes and the number of k-cycles (k=3..). This is the online version
Sa_672
Degree= 7, Diameter = 4; Order =672; Moore bound=1814
Obtained as a Cayley graph for semidirect product of Zm with Zn
Z_6*(39)Z_112 [2,73]<>[4,23], [5,54]<>[1,22], [5,71]<>[1,31], [3,42] avg.dist 3.496274
M. Sampels.
Large networks with small diameter.. In: Rolf H. Mohring (Ed.):
23rd International Workshop on Graph-Theoretic Concepts in Computer Science (WG '97), Lecture Notes in Computer Science 1335, pp. 288-302, Springer-Verlag, 1997 ISBN 3-540-63757-5. Communicated July 29, 1997
Download the raw adjacency list of the graph in NetworkX format (vertices labeled 0,2,...671) .
Other instances (F.Comellas 2024)
Z_6*(23)Z_112 [2,95]<>[4,97], [1,77]<>[5,21], [5,36]<>[1,68], [3,56] Avg.dist 3.496274 transm. 2346 adjlist NX
Z_6*(23)Z_112 [1,102]<>[5,54], [2,51]<>[4,45], [5,83]<>[1,107], [3,42] Avg.dist 3.496274 transm. 2346 adjlist NX
Z_6*(23)Z_112 [4,101]<>[2,107], [5,64]<>[1,96], [5,101]<>[1,29], [3,84] Avg.dist 3.496274 transm. 2346 adjlist NX
Z_6*(23)Z_112 [2,65]<>[4,31], [1,22]<>[5,38], [5,85]<>[1,61], [3,98] Avg.dist 3.496274 transm. 2346 adjlist NX
Z_6*(39)Z_112 [2,23]<>[4,41], [1,0]<>[5,0], [1,103]<>[5,95], [3,28] Avg.dist 3.496274 transm. 2346 adjlist NX
Z_6*(39)Z_112 [2,5]<>[4,43], [5,73]<>[1,65], [1,28]<>[5,28], [3,0] Avg.dist 3.496274 transm. 2346 adjlist NX
Z_6*(39)Z_112 [4,57]<>[2,103], [5,30]<>[1,62], [1,101]<>[5,29], [3,42] Avg.dist 3.496274 transm. 2346 adjlist NX
Z_6*(39)Z_112 [5,48]<>[1,32], [2,9]<>[4,55], [5,33]<>[1,57], [3,84] Avg.dist 3.496274 transm. 2346 adjlist NX
--------------------
This SageMath script computes several properties of two of the graphs including symmetry group sizes. This is the online version .
Loz_1100
Degree= 8, Diameter = 4; Order =1100; Moore bound=3201
Communicated by Eyal Loz, Math Dep., Auckland Univ., New Zealand (July 2006)
Voltage graph Z_20 x(2) Z_55, B(0,4), voltages [(4, 27)(12, 11)(9,9)(19, 11)], avg. dist.: 3.547771
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].
Download the raw adjacency list of the graph.
Link to Eyal Loz's data (internet archive) .
Found also as a semidirect product, some instances have a lower average distance (F.Comellas 2023):
Z_20 x(2) Z_55 with generators [1,45]<>[19,5]:[12,47]<>[8,13]:[11,39]<>[9,52]:[16,26]<>[4,24]. Avg. dist. 3.547771 (1,8,56,361,674) trans.: 3899 adjlist NX
Z_20 x(3) Z_55 with generators [9,8]<>[11,9]:[1,39]<>[19,42]:[8,1]<>[12,24]:[12,22]<>[8,33]. Avg. dist. 3.536852 (1,8,56,373,662) trans.: 3887 adjlist NX
Z_20 x(3) Z_55 with generators [1,33]<>[19,44]:[8,13]<>[12,37]:[9,2]<>[11,16]:[12,44]<>[8,11]. Avg. dist. 3.536852 (1,8,56,373,662) trans.: 3887 adjlist NX
Z_20 x(8) Z_55 with generators [16 9]<>[4 41]:[7 10]<>[13 50]:[17 12]<>[3 16]:[12 8]<>[8 37]. Avg. dist. 3.547771 adjlist NX
Z_20 x(8) Z_55 with generators [12,54]<>[8,16]:[16,2]<>[4,3]:[13,16]<>[7,23]:[17,37]<>[3,31]. Avg. dist. 3.547771 adjlist NX
Z_20 x(38) Z_55 with generators [7,18]<>[13,16]:[16,54]<>[4,31]:[3,35]<>[17,5]:[4,48]<>[16,2]. Avg. dist. 3.536852 (1,8,56,373,662) trans.: 3887 adjlist NX
Z_20 x(47) Z_55 with generators [8,43]<>[12,42]:[11,8]<>[9,34]:[19,17]<>[1,26]:[12,54]<>[8,16]. Avg. dist. 3.536852 (1,8,56,373,662) trans.: 3887 adjlist NX
Z_20 x(48) Z_55 with generators [11,5]<>[9,40]:[19,16]<>[1,2]:[12,3]<>[8,17]:[8,11]<>[12,44]. Avg. dist. 3.536852 (1,8,56,373,662) trans.: 3887 adjlist NX
--------------------
This SageMath script computes several properties of two of the graphs including symmetry group sizes. This is the online version .
Com_1640
Degree= 9, Diameter = 4; Order =1640; Moore bound=5266.
Cayley graph. Found as a semidirect product, 1640 nodes and 7380 (F.Comellas 2024):
- Z_40 x(22) Z_41, generators [23,14]<>[17,33]:[25,18]<>[15,13]:[27,35]<>[13,33]:[2,23]<>[38,8]:[20,3]<>[20,3]. Avg. dist.: 3.571080 (1,9,72,532,1026) transmission: 5853. adjlist NX
Z_40 x(24) Z_41, generators [25,28 ]<>[15,2 ]:[14,40 ]<>[26,33 ]:[29,11 ]<>[11,39 ]:[39,12 ]<>[1,40 ]:[20,35 ]<>[20,35 ]. Avg. dist.: 3.571080 (1,9,72,532,1026) transmission: 5853. adjlist NX
The two graphs are isomorphic.
--------------------
This SageMath script computes several properties of the graphs including symmetry group sizes. This is the online version .
--------------------
Former result, Order =1550
Communicated by Eyal Loz, Math Dep., Auckland Univ., New Zealand (July 2006)
Voltage graph Z_10 x(4) Z_155, B(1,4), voltages [(5, 0)|(7, 1)(4, 52)(6, 136)(1, 72)], avg. dist.: 3.555197
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].
Download the raw adjacency list of the graph.
Link to Eyal Loz's data (internet archive)
Found also as a semidirect product (F.Comellas 2023):
Z_10 x(4) Z_155 with generators [9,55]<>[1,90]:[6,126]<>[4,139]:[3,98]<>[7,13]:[6,142]<>[4,73]:[5,31]. Avg. dist. 3.555197 adjlist NX
Z_10 x(39) Z_155; generators [6,79]<>[45,6]:[9,1]<>[1,116]:[6,57]<>[4,113]:[3,130]<>[7,50]:[5,124]. Avg. dist. 3.555197 adjlist NX
Z_10 x(64) Z_155 with generators[9,132]<>[1,77]:[8,153]<>[2,132]:[7,19]<>[3,34]:[2,71]<>[8,114]:[5,0]. Avg. dist. 3.555197 adjlist NX
Dhar_2485
Degree= 10, Diameter = 4; Order =2485; Moore bound=8201.
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.
Cayley graph of the metacyclic group Z_35 x|_t Z_71, m=35, k=71, t=2 (order of t mod k is 35).
Group law: (x,y)*(u,v) = ((x+u) mod m, (y*t^u + v) mod k); identity (0,0); vertex id = x*k + y.
Generating set (10 elements, closed under inverses):
(18,57) (17,13) (12,66) (23,3) (29,12) (6,13) (33,22) (2,54) (14,27) (21,35). Download the raw adjacency list .
Former result
(10,4)=2331. Cayley graphs. Found as semidirect products, 2331 vertices, 11655 edges (F.Comellas 2024):
Z_9 x(44) Z_259, generators [8,132] [2,171] [2,71] [4,236] [6,240]. Avg. dist.: 3.580258 (1,10,90,768,1462) transmission: 8342. adjlist NX
This SageMath script computes several properties of the four graphs including symmetry group sizes. This is the online version .
Q7(T4)+
Degree = 11, Diameter = 4; Order = 3220; Moore bound=12222 ;
Graph constructed with the help of AI tools by Petrit Isufi (isufi.petrit@proton.me; Wuppertal, Germany. August 17, 2026).
After constructing Q7(T4) based on the published details (see below), as the graph is regular, no new vertices can be added without increasing the degrees. Edges are deleted and each deletion is accepted only after an exact re-check that the diameter is still 4, then new vertices are added one at a time by exact CP-SAT, each joined only to freed vertices, none joined to each other. After 215 deletions and 20 new vertices, the final graph has 3220 nodes and 17605 edges, maximum degree 11, and diameter 4, average degree 10.935, degree histogram [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 210, 3010] and avg. dist.: 3.662781.
Download the edge list of the graph.
This SageMath script computes several properties of the graph. This is the online version .
Former results
** (11,4)=3202. 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 .
** (11,4)=3200. Q7(T4) J. Gomez, M.A. Fiol. Dense Compound Graphs.Ars Combinatoria, 20-A (1985), pp. 211-237. link to the paper
Q′8*X8+
Degree = 12, Diameter = 4; Order=4707; Moore bound= 17569;
Graph constructed with the help of AI tools by Petrit Isufi (isufi.petrit@proton.me; Wuppertal, Germany. August 27, 2026).
An improvement on the former entry with 4705 graph. That graph has 223 vertices of degree below 12 ("free stubs"), so a search an exact CP-SAT model whether new vertices can be attached to those free slots without
breaking diameter 4 lead to that two could be, giving 4707; a third is infeasible on that pinned choice, which is not a proof that 4708 is impossible. The new graph has | Ord.: 4707 / Size: 28142 / Diam.: 4 / Avg.dist: 3.72432 / Girth: 3 /
Degree histogram : [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 200, 4507]
Download the edge list of the graph.
This SageMath script computes several properties of the graph. This is the online version .
Former result, order 4705.
Graph constructed with the help of AI tools by Petrit Isufi (isufi.petrit@proton.me; Wuppertal, Germany. August 17, 2026).
After constructing Q′8*X8 based on the published details (Delorme's q = 8 polarity quotient, star-multiplied with the X8 factor of Bermond-Delorme-Farhi) a graph with 4680 vertices, 27820 edges, degree distribution 520 x 11 + 4160 x 12, maximum degree 12, diameter 4, is obtained. Then 25 new vertices were added (with no edges between the new vertices; every new edge is incident with a vertex of degree 11 in the former graph) obtaining a new graph with 4705 vertices, 28118 edges, maximum degree 12, and diameter 4. The greedy search method could not add a 26th vertex. The new graph has order.: 4705 / size: 28118 / diam.: 4 / avg.dist: 3.72455 / girth: 3 / degree histogram [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 222, 4482]
Download the edge list of the graph.
This SageMath script computes several properties of the graph. This is the online version .
Former result, order 4680.
Q′8*X8 with 4680 vertices. Special product of bibartite graphs from C. Delorme.
C. Delorme. Grands graphes de degré et diamètre donnés.Eur. J. Comb. 6 (1985), pp. 291-302. (submitted 1982) link to the paper
Q9(T4)+
Degree = 13, Diameter = 4; Order= 6587; Moore bound= 24506;
Graph constructed with the help of AI tools by Petrit Isufi(isufi.petrit@proton.me; Wuppertal, Germany. August 17, 2026).
After constructing Q9(T4) based on the published details (see below), as the graph is regular, no new vertices can be added without increasing the degrees. Edges are deleted and each deletion is accepted only after an exact re-check that the diameter is still 4, then new vertices are added one at a time by exact CP-SAT, each joined only to freed vertices, none joined to each other. After 290 deletions and 27 new vertices, the final graph has 6587 nodes and 42701 edges, maximum degree 13, and diameter 4, average degree 12.965 , degree histogram [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 229, 6358] and avg. dist.: 3.715966.
Download the edge list of the graph.
This SageMath script computes several properties of the graph. This is the online version .
Former result
(13,4)=6560. Q9(T4); J. Gomez, M.A. Fiol. Dense Compound Graphs.Ars Combinatoria, 20-A (1985), pp. 211-237. link to the paper
Q9(T5)+
Degree = 14, Diameter = 4; Order =8255; Moore bound= 33321;
Graph constructed with the help of AI tools by Petrit Isufi (isufi.petrit@proton.me; Wuppertal, Germany. August 17, 2026).
After constructing Q9(T5) based on the published details (see below), as the graph is regular, no new vertices can be added without increasing the degrees. Edges are deleted and each deletion is accepted only after an exact re-check that the diameter is still 4, then new vertices are added one at a time by exact CP-SAT, each joined only to freed vertices, none joined to each other. After 417 deletions and 55 new vertices, the final graph has 8255 nodes and 57747 edges, maximum degree 14, and diameter 4, average degree 13.99 , degree histogram [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 2, 72, 8181] and avg. dist.: 3.736110 .
Download the edge list of the graph.
This SageMath script computes several properties of the graph. This is the online version .
Former result
(14,4)=8200. Q9(T5); J. Gomez, M.A. Fiol. Dense Compound Graphs.Ars Combinatoria, 20-A (1985), pp. 211-237. link to the paper
Q11(T4)+
Degree = 15, Diameter = 4; Order =11736; Moore bound = 44326 ;
Graph constructed with the help of AI tools by Petrit Isufi (isufi.petrit@proton.me; Wuppertal, Germany. August 19, 2026).
After constructing Q11(T4) based on the published details (see below), as the graph is regular, no new vertices can be added without increasing the degrees. Edges are deleted and each deletion is accepted only after an exact re-check that the diameter is still 4, then new vertices are added one at a time by exact CP-SAT, each joined only to freed vertices, none joined to each other. After 382 deletions and 24 new vertices, the final graph has 11736 nodes and 87814 edges, maximum degree 15, and diameter 4, average degree 14.965 , degree histogram [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 410, 11325] and avg. dist.: 3.748630 .
Download the edge list of the graph.
Former result
(15,4)=11712. Q11(T4); J. Gomez, M.A. Fiol. Dense Compound Graphs.Ars Combinatoria, 20-A (1985), pp. 211-237. link to the paper
Q11(T5)+
Degree = 16, Diameter = 4; Order =14687; Moore bound=57857 ;
Graph constructed with the help of AI tools by Petrit Isufi (isufi.petrit@proton.me; Wuppertal, Germany. August 19, 2026).
After constructing Q11(T5) based on the published details (see below), as the graph is regular, no new vertices can be added without increasing the degrees. Edges are deleted and each deletion is accepted only after an exact re-check that the diameter is still 4, then new vertices are added one at a time by exact CP-SAT, each joined only to freed vertices, none joined to each other. After 400 deletions and 47 new vertices, the final graph has 14687 nodes and 117451 edges, maximum degree 16, and diameter 4, average degree 15.994, degree histogram [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 5, 75, 14606] and avg. dist.: 3.770451.
Download the edge list of the graph.
Former result
(16,4)=14640. Q11(T5); J. Gomez, M.A. Fiol. Dense Compound Graphs.Ars Combinatoria, 20-A (1985), pp. 211-237. link to the paper