The (Degree, Diameter) Problem for Graphs


My home page at UPC (Universitat Politècnica de Catalunya) is Francesc Comellas
A snapshot of the full contents of this page, as of January 28, 2026 - including subdirectories, graph descriptions, adjacency lists, figures, and other files?can be downloaded from "Table of Large Degree/Diameter Graphs", Mendeley Data (2026) -120 MB - doi: 10.17632/d75dzbjd4k. . See also "Table of large graphs with given degree and diameter". doi: 10.48550/arXiv.2406.18994v2 [Co26].
This web page, along with all associated pages and files, is AI-free (except for some SageMath scripts that were created with the help of ChatGPT).

A graph, G=(V,E), consists of a non empty finite set V of elements called vertices and a set E of pairs of elements of V called edges. The number of vertices N=|G|=|V| is the order of the graph. If (x,y) is an edge of E, we say that x and y (or y and x) are adjacent and this is usually written x --> y. It is also said that x and y are the endvertices of the edge (x,y). The degree of a vertex δ(x) is the number of vertices adjacent to x. The degree of G is Δ=max_{x ∈ V} δ(x). A graph is regular of degree Δ or Δ - regular if the degree of all vertices equal Δ. The distance between two vertices x and y, d(x,y) , is the number of edges of a shortest path between x and y , and its maximum value over all pair of vertices, D=max_{x, y ∈ V}d(x,y) , is the diameter of the graph. A (Δ,D) graph is a graph with maximum degree Δ and diameter at most D. The order of a graph with degree Δ, Δ > 2), of diameter D is easily seen to be bounded by

1 + Δ + Δ (Δ-1) + ...+ Δ (Δ-1) D-1 = (Δ (Δ-1)D -2) / (Δ-2) = N(Δ, D)

Hoffman and Singleton introduced the concept of Moore graphs, after Edward Forrest Moore, as graphs attaining this value, known as Moore bound. They also showed that, for D ≥ 2 and Δ ≥ 3, Moore graphs exist for D=2 and Δ =3,7 , and (perhaps) 57, see [HoSi60]. In this context, it is of great interest to find graphs which for a given maximum diameter and maximum degree have a number of vertices as close as possible to the Moore bound.

The following table give the state of the art regarding the LARGEST KNOWN (Δ ,D)-GRAPHS. Entries in boldface are optimal. Entries with ∗ are Cayley graphs or a former entry is a Cayley graph (click for details).

Click a position to view more information about that entry, such as graph construction details, the Moore bound, author, references, and more. Entries with a border include a SageMath script to compute their relevant properties. Adjacency lists are available for download for most graphs with small order (fewer than 20,000).

LARGEST KNOWN (Δ,D)-GRAPHS

⚠ Warning: Table values will be updated as they arrive, but it may take a few days.
Details for the new updates (order > 20000) will be available via each entry link around the 15th of each month..

Click on the value to get information about the graph (author, reference, adjacency list, etc.)

Δ   \ D  2 3 4 5 6 7 8 9 10
3 10 20 38 70 132 200 360 600 1 250
4 15 41 104 364 760 1 344 3 243 7 884 19 306
5 24 72 252 ∗ 650 2 836 6 000 18 810 ∗ 60 686 202 550
6 ∗ 32 120 441 ∗ 1 518 8 802 ∗ 20 400 ∗ 80 050 ∗ 331 387 ∗ 1 394 189
7 50 ∗ 170 ∗ 684 ∗ 2 810 ∗ 12 654 ∗ 56 952 ∗ 264 440 ∗ 1 332 774 ∗ 6 645 690
8 57 ∗ 253 ∗ 1 100 ∗ 5 334 40 560 ∗ 139 679 ∗ 802 890 ∗ 4 601 361 ∗ 27 019 307
9 74 585 ∗ 1 770 ∗ 9 020 77 418 ∗ 309 510 ∗ 1 961 496 ∗ 13 219 318 ∗ 89 658 816
10 91 650 ∗ 2 566 ∗ 33 397 137 180 ∗ 624 690 ∗ 4 524 979 ∗ 34 913 494 ∗ 265 782 337
11 106 715 3 654 ∗ 37 628 186 033 ∗ 1 197 748 ∗ 9 739 368 ∗ 81 961 120 ∗ 697 429 356
12 133 810 6 156 ∗ 42 342 364 032 ∗ 2 115 075 ∗ 19 218 539 ∗ 179 227 730 ∗ 1 693 183 778
13 162 973 6 804 ∗ 51 417 538 740 ∗ 3 691 038 ∗ 36 275 160 ∗ 362 847 996 ∗ 3 789 512 750
14 183 ∗ 1 208 9 720 ∗ 94 186 824 124 ∗ 6 200 460 ∗ 65 587 703 ∗ 709 728 527 ∗ 8 052 194 837
15 190 1 620 15 552 ∗ 102 060 1 428 361 ∗ 9 758 988 ∗ 110 182 818 ∗ 1 315 254 800 ∗ 16 021 302 724
16 ∗ 216 1 920 16 384 153 600 1 793 786 ∗ 14 995 367 ∗ 185 488 215 ∗ 2 345 620 783 ∗ 29 976 204 593

Updates after 1980.
Please, send new results to: francesc.comellas@upc.edu ( Francesc Comellas, who maintains this WWW table).
See also the Combinatorics Wiki web site

  References

Created: January, 1995 in collaboration with Charles Delorme. Last changed: November 4, 2026.
Go back in time and have a snapshot of this table at different moments after 1995 thanks to the internet archive project.