The (Degree,Diameter) Problem for Graphs

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:

• Geoff Exoo, yellow: March 7 and 18, 2005 (4,7) (5,5); August 22,28, 2004; (7,3) [16]. June 9, 1999; (5,5). July 17, 1998; (3,6) [14]. July 12, 1998; (6,4). July 1, 1998; (3,7),(3,8);(6,4). May 22, 1998; (16,2), (4,4), (5,3), (6,3) [12]. May 19, 1998; (7,3) [12].;
• P. Hafner, light blue: Jul 1997 - Jul 1998; (5,9), (5,10), (6,7-10), (7,6-9),(8,5), (8,7-10), (9,7-10), (10,5), (10,7-10), (11,5), (11,7-8), (12,7), (13,5), (13,7), (14,5), (15,8), see [5].
• Jean-Jacques Quisquater, creme: Feb 27, 1998; (3,9), (3,10) [11].
• J. Gomez, I. Pelayo, green: Feb 20, 1998; (8,6), (10,6), (12,6), (14,6). Jul 30, 1997; (5,6), (6,6), (9,6) [10].
• M. Sampels, blue: Jul-Dec, 1997; (9,4), (9,5), (10,5), (7,6), (6,7), (7,7), (10,7), (4-10,8), (5-10,9), (4-8,10), (9-10,10) [9].
• P. Hafner, light blue: Jul 14 1997; (12,7), (13,7) [5]. Apr 24, 1997; (13,8) [5].
• B.D. McKay, M. Miller and J. Siran, pink: Mar 12, 1997; (11,2), (13,2) [6].
• P. Hafner, light blue: 2000; Jan 2003; (7,10), (14,8) [14].
• J. Gómez, light green: 2005; April 2005; (13,10),(15,7),(15,10) [personal comm.]; 2003; Jun 2003; (5,6), (8,6), (9,6), (10,6), (12,6), (14,6). [15]

Click here for a JPEG (64 KB) image of the table

General references and recent results

1. N. Biggs; Algebraic Graph Theory, Cambridge Math. Library ISBN 0-521-45897-8 pbk, (1974, 1993 (2nd edition)).
2. J.-C. Bermond, C. Delorme and J.J. Quisquater; Table of large ( D  ,D)-graphs. Discrete Applied Mathematics, 37/38 (1992), 575-577.
3. 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.)
4. M.J. Dinneen & P. Hafner. New results for the degree/diameter problem. Networks, 24 (1994) 359-367.
5. 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
6. 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.
7. M. Sampels (msampels@ulb.ac.be ) & S. Schöf. Massively parallel architectures for parallel discrete event simulation. Proceedings of the 8th European Simulation Symposium (ESS'96), vol. 2, (1996), pp. 374-378.
8. 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.
9. 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
10. J. Gómez, I. Pelayo and C. Balbuena. New large graphs with given degree and diameter six. Networks, 34 (1999), 154-161.
11. Jean-Jacques Quisquater. Chordal rings. Communicated February 27, 1998)
12. 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
13. Michael Sampels. Algebraische Konstruktion effizienter Verbindungsnetzwerke. PhD thesis at the University of Oldenburg. Logos-Verlag Berlin, 1998. ISBN 3-89722-051-2.
14. P.R. Hafner (hafner@math.auckland.ac.nz ). Communicated January 6, 2003.


15. J. Gómez. (jgomez@mat.upc.es). On large (D,6)-graphs. Submitted (2003).
16. Geoffrey Exoo (ge@ginger.indstate.edu). (4,7)=1200. Communicated March 7, 2005; (7,3)=156. Communicated August 22-28, 2004.
 

 

Related problems are:

• The (Degree, Diameter) problem for planar graphs. James Preen keeps several tables for the ( D,D) problem for planar graphs , that formerly were maintained by Rob Pratt here (copy maintained at web.archive.org).
   Erich Friedman had also a table of Large Regular Planar Graphs with Small Diameter (copy maintained at web.archive.org).
• The ( D ,D) problem for planar graphs proposed to kids, Megamath (LANL)
• The (D,D) vertex symmetric digraph problem . We keep also a Table of largest known ( D,D) vertex symmetric digraphs .
• The (D,D,D, 1)- graph problem. The corresponding Table of largest known ( D, D,D, 1)- graphs is also in this place.

---

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