A resource for the DegreeDiameter Problem
ΔD Table
The table gives the state of the art with respect to the largest known (Δ,D)graphs.
If you don't see the background colours of the table cells, you may use this direct link (http://wwwma4.upc.es/~comellas/deltad/taula_delta_d.html) to the table (in each cell, the background colour indicates the author).
Entries in boldface are optimal.
Δ \ D  2  3  4  5  6  7  8  9  10 

3  10  20  38  70  132  196  336  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  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 
A World Combinatorics Exchange resource at
http://wwwma4.upc.es/~comellas/deltad/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 in V} ∂(x). A graph is regular of degree Δ or Δregular if the degree of all vertices equals Δ. 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)graph is a graph with maximum degree Δ and diameter at most D. The order of a graph with degree Δ (Δ> 2) of diameter D is bounded by the Moore bound.
Recent updates:
Please, send new results to: cd@lri.fr (Charles Delorme, LRI, who keeps the LaTeX table) comellas@ma4.upc.edu (Francesc Comellas, DMAT, who updates this WWW table).
It is known that, for D ≥ 2 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.
For some values in the table you may download the adjacency list and/or the Cabri file. (Download the Cabri program to study graphs from here).
Recent updates:
 Eduardo Canale: August 22, 2012 (15,2).
 Alexis Rodriguez/Eduardo Canale: June 30, 2012 (9,5), August 20, 2012 (6,9).
 G. Exoo, yellow: May 21, 2010 (5,4); May 19, 2010 (4,4), (6,3); January 28, 2008 (3,7), (3,8), (3,9); July 27, 2006 (4,7); May 13, 2006 (11,2); November 1224 2005 (3,7); November 1, 2005 (7,3); September 12, 2005 (3,9); May 24, 2005 (3,10); July 17, 1998 (3,6); July 1, 1998 (3,8); May 22, 1998 (16,2), (4,4), (5,3), (6,3) [Ex01]; May 19, 1998 (7,3) [Ex01].
 JeanJacques Quisquater, violet: October 19, 2007; (3,9) [Qu07].
 J. Gómez, lime: September 10, 2006; (12,3),(13,3),(14,3) [Go06].
 Marston Conder, salmon: August 17, 2006 (3,10) [Co06].
 E. Loz, orange: November and August 2006: Most values for degrees 410 and diameter 5 and 710. See [Lo06] for more details while the descriptions are not updated; July 311, 2006 (4,8),(4,9),(4,10), (5,5),(5,7),(5,8),(6,4),(6,5),(6,7),(6,8),(7,6),(8,4),(8,5),(9,4),(9,5),(10,4),(10,5),(11,5) [Lo06].
 G. PinedaVillavicencio, J. Gómez, M. Miller, H. PérezRosés, green: July 27, 2006 (5,6), (6,6), (9,6), (12,6), (14,6) [PiGoMiPe06].
 J. Gómez, M. Miller; light green: April 2005; (13,10),(15,7),(15,10) [GoMi06].
 J. Gómez, olive; June 2003; (8,6), (10,6) [Go05].
 P. Hafner; blue: Jan 2003 (7,10), (14,8); Jul 1997  Jul 1998 (5,9), (5,10), (6,7), (6,8),(6,9),(6,10), (7,6),(7,8),(7,9),(8,5), (8,7), (8,8),(8,9),(8,10), (9,7),(9,8),(9,9),(9,10), (10,5), (10,7), (10,8),(10,9),(10,10), (11,5), (11,7),(11,8), (12,7), (13,5), (13,7), (14,5), (15,8), see [Ha95]; Jul 14 1997; (12,7), (13,7) [5]. Apr 24, 1997; (13,8) [5].
 C. Delorme, J. Gómez; mediumgreen 2002 (11,9) (12,9) (13,9) (14,9) [DeGo02].
 B.D. McKay, M. Miller, J. Siran; pink: Mar 12, 1997 (13,2) [McMiSi98].
 M. Sampels; light blue 1997 (5,4) (7,4) [Sa97,Sa98].
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, 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.
General references and recent results  

Related problems are:

Share: