Combinatorics, Graph Theory and Applications. COMBGRAF

A resource for the Degree-Diameter Problem

Δ-D Table


The table gives 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...

If you don't see the background colours of the table cells, you may use this direct link (http://www-ma4.upc.es/~comellas/delta-d/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://www-ma4.upc.es/~comellas/delta-d/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 Δ = maxx 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=maxx, 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.

 

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 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.

Please, send new results to: cd@lri.frThis email address is being protected from spam bots, you need Javascript enabled to view it (Charles Delorme, LRI, who keeps the LaTeX table) comellas@ma4.upc.eduThis email address is being protected from spam bots, you need Javascript enabled to view it (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

  • [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.eduThis email address is being protected from spam bots, you need Javascript enabled to view it). 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.esThis email address is being protected from spam bots, you need Javascript enabled to view it ). 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.nzThis email address is being protected from spam bots, you need Javascript enabled to view it); 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.nzThis email address is being protected from spam bots, you need Javascript enabled to view it). 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.
  • [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.beThis email address is being protected from spam bots, you need Javascript enabled to view it) & 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.beThis email address is being protected from spam bots, you need Javascript enabled to view it). 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: