## 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:

• 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 12-24 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].;
• Jean-Jacques 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 4-10 and diameter 5 and 7-10. See [Lo06] for more details while the descriptions are not updated; July 3-11, 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. Pineda-Villavicencio, J. Gómez, M. Miller, H. Pérez-Rosé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.
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

• [BeDeQu92] J.-C. Bermond, C. Delorme and J.J. Quisquater; Table of large (Δ,D)-graphs. Discrete Applied Mathematics, 37/38 (1992), 575-577.
• [Bi74] N. Biggs; Algebraic Graph Theory, Cambridge Math. Library ISBN 0-521-45897-8 pbk, (1974, 1993 2nd edition).
• [Co06] Marston Conder http://www.math.auckland.ac.nz/~conder/symmcubic2048list.txt
• [CoGo92] F. Comellas and J. Gómez, New large graphs with given degree and diameter. , Graph Theory, Combinatorics and Algorithms, vol 1, Yousef Alavi and Allen Schwenk (Eds.), John Wiley & Sons, Inc.; New York (1995) pp. 221-233. ISBN 0-471-30437-9. (Proc. of the Seventh Quadrennial International Conference on the Theory and Applications of Graphs, Kalamazoo, MI, USA, June 1992.)
• [DeGo02] C. Delorme, J. Gómez. Some new large compound graphs. European Journal of Combinatorics, 23 (2002), pp. 547.
• [DiHa94] M.J. Dinneen & P. Hafner. New results for the degree/diameter problem. Networks, 24 (1994) 359-367.
• [Ex01] Geoffrey Exoo (ge@ginger.indstate.edu ). A family of graphs and the degree/diameter problem.  J. Graph Theory 37 (2001), 118-124. Communicated May, 19-22,  July, 1 1998
• [GoFiSe93] J. Gómez, M.A. Fiol and O. Serra, On large (Δ, D) graphs, Discrete Mathematics, 114 (1993), pp. 235.
• [GoPeBa99] J. Gómez, I. Pelayo and C. Balbuena. New large graphs with given degree and diameter six. Networks, 34 (1999), 154-161.
• [Go05] J. Gómez. (jgomez@mat.upc.es). On large (Δ,6)-graphs. Networks 46 (2005), pp. 82-87.
• [Go06] J. Gómez. Some new large (Δ,3) graphs. Submitted 2006.
• [GoMi06] J. Gómez Martí, M. Miller. Two new families of large compound graphs. Networks 47 (2006) pp. 140-146.
• [Gu00] X. Guarch (sup: F. Comellas), Contruction of dense interconnection networks and cages using simulated annealing, PFC (equiv. Master Thesis), ETSETB, Universitat Politecnica de Catalunya, January 12, 2000 (in Catalan).
• [Ha94] P.R. Hafner (hafner@math.auckland.ac.nz ); Large Cayley graphs and digraphs with small degree and diameter. Report CDMTCS-005, June 1995. Wieb Bosma and Alf van der Poorten (eds) Computational Algebra and Number Theory Mathematics and Its Applications 325; Kluwer Academic Publishers Dordrecht/Boston/London (1995), pp. 291--302; ISBN 0-7923-3501-5
• [Lo06] Eyal Loz ( eloz002@math.auckland.ac.nz ). Ongoing PhD Thesis. Communicated July & August 2006. See http://www.math.auckland.ac.nz/~eloz002/degreediameter/ for more details.
• [McSi98] B.D. McKay, M. Miller, J. Siran; A note on large graphs of diameter two and given maximum degree .   J. Combin. Theory Ser. B 74 (1998) 110-118.
• [MiSi05] Mirka Miller and Jozef Siran. Moore graphs and beyond: A survey of the degree/diameter problem. Electron. J. Combin. DS14 (December 5, 2005) 61 pp.
• [Mo06] S.G. Molodtsov. Largest graphs of diameter 2 and maximum degree 6. LNCS 4123 (2006) 853-857.
• [PiGoMiPe06] G. Pineda-Villavicencio, J. Gómez, M. Miller, H. Pérez-Rosés. New largest graphs of diameter 6. Electronic Notes in Discrete Mathematics 24 (2006) 153-160.
• [Qu07] J.-J. Quisquater (jjq (at) dice.ucl.ac.be ). Communicated October 19, 2007.
• [Sa96] M. Sampels (msampels@ulb.ac.be ) & S. Schof. Massively parallel architectures for parallel discrete event simulation. Proceedings of the 8th European Simulation Symposium (ESS'96), vol. 2, (1996), pp. 374-378.
• [Sa97] M. Sampels (msampels@ulb.ac.be ). Proceedings of the 23rd International Workshop on Graph-Theoretic Concepts in Computer Science (WG '97), LNCS 1335, pp. 288-302. Springer-Verlag, 1997. Communicated July 29, 1997
• [Sa98 ] Michael Sampels. Algebraische Konstruktion effizienter Verbindungsnetzwerke. PhD thesis at the University of Oldenburg. Logos-Verlag Berlin, 1998. ISBN 3-89722-051-2.
• [Wo96] O. Wohlmuth. A New Dense Group Graph Discoverd by an Evolutionary Approach . Paralleles und Verteiltes Rechnen Beitraege zum 4. Workshop ueber Wissenschaftlichen Rechnen, p. 21-27, Shaker Verlag 1996. ISBN 3-8265-1826-8.

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.