The (Degree, Diameter) Problem for Graphs


My home page at UPC (Universitat Politècnica de Catalunya) is Francesc Comellas
You can download the full contents of this page (including subdirectories, descriptions and adjacency list of the graphs, figures, etc. aprox. 120 MB ) from "Table of Large Degree/Diameter Graphs", Mendeley Data (2026), 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: 🛠 Updating !)

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 753 1 320 3 243 7 832 18 436
5 24 72 252 ∗ 650 2 820 5 896 17 724 ∗ 59 294 190 578
6 ∗ 32 120 441 ∗ 1 518 8 802 ∗ 20 400 ∗ 78 825 ∗ 331 387 ∗ 1 279 794
7 50 ∗ 170 ∗ 684 ∗ 2 810 ∗ 12 642 ∗ 56 952 ∗ 255 938 ∗ 1 227 774 ∗ 6 128 958
8 57 ∗ 253 ∗ 1 100 ∗ 5 334 40 560 ∗ 137 247 ∗ 744 942 ∗ 4 260 050 ∗ 25 700 510
9 74 585 ∗ 1 640 ∗ 8 856 77 418 ∗ 300 518 ∗ 1 859 260 ∗ 12 441 690 ∗ 80 560 386
10 91 650 ∗ 2 485 ∗ 33 397 137 180 ∗ 605 607 ∗ 4 387 768 ∗ 31 090 100 ∗ 239 005 058
11 106 715 3 444 ∗ 37 628 186 033 ∗ 1 153 512 ∗ 9 261 072 ∗ 74 391 834 ∗ 634 001 048
12 133 810 5 832 ∗ 42 342 364 032 ∗ 2 031 500 ∗ 18 101 302 ∗ 164 003 466 ∗ 1 545 004 522
13 162 873 6 615 ∗ 51 417 535 302 ∗ 3 529 240 ∗ 35 140 270 ∗ 334 485 050 ∗ 3 480 003 090
14 183 ∗ 1 116 8 303 ∗ 88 452 824 124 ∗ 6 200 460 ∗ 58 673 788 ∗ 640 002 162 ∗ 7 360 000 970
15 190 1 539 11 785 ∗ 100 000 1 424 474 ∗ 9 372 780 ∗ 98 108 874 ∗ 1 200 000 050 ∗ 13 600 000 810
16 ∗ 216 1 920 16 384 147 456 1 783 834 ∗ 14 882 658 ∗ 162 001 414 ∗ 2 120 003 902 ∗ 22 500 000 906

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: October 14, 2026.
Go back in time and have a snapshot of this table at different moments after 1995 thanks to the internet archive project.