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.