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 δ(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

This value is called the Moore bound, and it is known that, for D2 and Δ ≥ 3, this bound is only attained if D=2 and Δ =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)-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@ma4.upc.edu ( Francesc Comellas , DMAT/combgraph , 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. August 2012.


D  \ D  2 3 4 5 6 7 8 9 10
3 10 20 38 70 132 196 336 600 1 250
15 41 98 364 740 1 320 3 243 7 575 17 703
5 24 72 212 624 2 772 5 516 17 030 53 352 164 720
6 32 111 390 1 404 7 917 19 282 75 157 331 387 1 212 117
7 50 168 672 2 756 11 988 52 768 233 700 1 124 990 5 311 572
8 57 253 1 100 5 060 39 672 130 017 714 010 4 039 704 17 823 532
9 74 585 1 550 8 268 75 893 270 192 1 485 498 10 423 212 31 466 244
10 91 650 2 223 13 140 134 690 561 957 4 019 736 17 304 400 104 058 822
11 104 715 3 200 18 700 156 864 971 028 5 941 864 62 932 488 250 108 668
12 133 786 4 680 29 470 359 772 1 900 464 10 423 212 104 058 822 600 105 100
13 162 851 6 560 39 576 531 440 2 901 404 17 823 532 180 002 472 1 050 104 118
14 183 916 8 200 56 790 816 294 6 200 460 41 894 424 450 103 771 2 050 103 984
15 187 1 215 11 712 74 298 1 417 248 8 079 298 90 001 236 900 207 542 4 149 702 144
16 198 1 600 14 640 132 496 1 771 560 14 882 658 104 518 518 1 400 103 920 7 394 669 856

References

Related problems are:


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