The (Degree, Diameter) Problem for Graphs

See also Combinatorics Wiki web site
A shortcut URL for this web page is: http://comellas.eu. My home page at UPC is Francesc Comellas
You can download its full content (subdirectories, descriptions and adjacency list of the graphs, figures, etc. ) by clicking here

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 with respect to the LARGEST KNOWN (Δ ,D)-GRAPHS

Click the position if you wish to know more information: graph construction details, Moore bound, author, references... For some values you may download the adjacency list. Entries in boldface are optimal. Updates after 1980:


Please, send new results to:
francesc.comellas@upc.edu ( Francesc Comellas , who updates this WWW table).

Link to a Java applet that computes the degree and diameter of a graph in a file, local or accessible by HTTP, and formatted as a list of adjacencies. Click here.

LARGEST KNOWN (Δ,D)-GRAPHS
Last update: (13, 3) August 6, 2021

Δ   \ D  2 3 4 5 6 7 8 9 10
3 10 20 38 70 132 196 360 600 1 250
4  15 41 98 364 740 1 320 3 243 7 575 17 703
5 24 72 212 624 2 772 5 516 17 030 57 840 187 056
6 32 111 390 1 404 7 917 19 383 76 461 331 387 1 253 615
7 50 168 672 2 756 11 988 52 768 249 660 1 223 050 6 007 230
8 57 253 1 100 5 060 39 806 131 137 734 820 4 243 100 24 897 161
9 74 585 1 550 8 268 76 228 279 616 1 697 688 12 123 288 65 866 350
10 91 650 2 286 13 140 134 830 583 083 4 293 452 27 997 191 201 038 922
11 104 715 3 200 19 500 156 864 1 001 268 7 442 328 72 933 102 600 380 000
12 133 786 4 680 29 470 359 926 1 999 500 15 924 326 158 158 875 1 506 252 500
13 162 856 6 560 40 260 531 440 3 322 080 29 927 790 249 155 760 3 077 200 700
14 183 916 8 200 57 837 818 094 6 200 460 55 913 932 600 123 780 7 041 746 081
15 187 1 215 11 712 76 518 1 417 248 8 599 986 90 001 236 1 171 998 164 10 012 349 898
16 200 1 600 14 640 132 496 1 771 560 14 882 658 140 559 416 2 025 125 476 12 951 451 931

  References

  Related problems are:

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