The (Degree,Diameter) Problem for Graphs

A World Combinatorics Exchange resource at
http://www-mat.upc.es/grup_de_grafs/grafs/taula_delta_d.html

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 Delta(x) is the number of vertices adjacent to x. The degree of G is D = \max_{x \in V} Delta(x). A graph is regular of degree D or D - regular if the degree of all vertices equal D  . 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 \in V}d(x,y) , is the diameter of the graph. A (D  ,D) graph is a graph with maximum degree D   and diameter at most D. The order of a graph with degree D(D  > 2) of diameter D is easily seen to be bounded by

This value is called the Moore bound, and it is known that, for D >= 2 and D >= 3, this bound is only attained if D=2 and D =3,7 , and (perhaps) 57, (see [1]). In this context, it is of great interest to find graphs which for a given 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  ,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 and/or the Cabri file. (Download the Cabri program to study graphs from here ). Entries in boldface are optimal. Recent updates:

A LaTeX dvi table and dvi legend are available from Charles Delorme, Laboratoire de Recherche en Informatique, Orsay, France.
Please, send new results to:
cd@lri.fr (Charles Delorme , LRI , who keeps the LaTeX table)
comellas@mat.upc.es ( Francesc Comellas , DMAT , 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.

Click here for a PNG (portable network graphic) image of the table -118 KB-

LARGEST KNOWN (D,D)-GRAPHS (August 2006)
D  \ D  2 3 4 5 6 7 8 9 10
3 10 20 38 70 132 192 330 576 972
4  15 41 96 364 740 1.296 3.243 7.575 17.703
5 24 72 210 624 2.772 5.516 17.030 53.020 164.700
6 32 110 390 1.404 7.917 19.282 74.800 294.679 1.211.971
7 50 168 672 2.756 11.988 52.404 233.664 1.085.580 5.311.566 
8 57 253 1.100 5.060 39.806 129.473 713.539 4.039.649 13.964.808
9 74 585 1.550 8.200 76.228 270.048 1.485.466 8.911.766 25.006.478
10 91 650 2.223 13.140 134.830 561.949 4.019.489 13.964.808 52.029.411
11 104 715 3.200 18.700 156.864 970.410 5.211.606 48.626.760 179.755.200
12 133 780 4.680 29.435 359.926 1.900.319 10.007.820 97.386.380 466.338.600
13 162 845 6.560 39.402 531.440 2.901.294 15.733.122 145.880.280 871.561.600
14 183 912 8.200 56.325 818.094 6.200.460 34.839.506 194.639.900 1.865.452.680
15 186 1.215 11.712 73.984 1.417.248 7.972.020 45.000.618 282.740.976 4.149.702.144
16 198 1.600 14.640 132.496 1.771.560 14.882.658 86.882.544 585.652.704 7.394.669.856

References

Related problems are:

Created: January, 1995; last changed: 2006/august/2
Go back in time and have a snapshot of this table at different moments after 1995 thanks to the internet archive project.