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 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: November 12, 18, 22, 24 2005 (6,4) (4,7) (3,7)(4,8); November 1, 2005 (7,3); September 16, 2005 (4,7); September 12, 2005 (3,9); May 24, 2005 (3,10); March 7 and
18, 2005 (4,7) (5,5) [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].
- 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) [with M.
Miller, personal comm.]; 2003; Jun 2003; (5,6), (8,6), (9,6), (10,6), (12,6),
(14,6). [15]
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@mat.upc.es ( 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.
Click here for a
JPEG (64 KB) image of the table
LARGEST KNOWN (D,D)-GRAPHS (November
2005)
General references and recent results
- N. Biggs; Algebraic Graph Theory, Cambridge Math. Library ISBN
0-521-45897-8 pbk, (1974, 1993 (2nd edition)).
- J.-C. Bermond, C. Delorme and J.J. Quisquater; Table of large ( D ,D)-graphs. Discrete Applied Mathematics,
37/38 (1992), 575-577.
- 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.)
- M.J. Dinneen & P. Hafner. New results for the
degree/diameter problem. Networks, 24 (1994) 359-367.
- 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
- 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.
- 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.
- 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.
- 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
- J. Gómez, I. Pelayo and C. Balbuena. New large graphs with given degree
and diameter six. Networks, 34 (1999), 154-161.
- 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).
- 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
- Michael Sampels. Algebraische Konstruktion effizienter
Verbindungsnetzwerke. PhD thesis at the University of Oldenburg. Logos-Verlag
Berlin, 1998. ISBN 3-89722-051-2.
- P.R. Hafner (hafner@math.auckland.ac.nz ).
Communicated January 6, 2003.
- J. Gómez. (jgomez@mat.upc.es). On
large (D,6)-graphs. Submitted (2003).
- Geoffrey Exoo (ge@ginger.indstate.edu). (4,8)=3087, (3,7)=192, (4,7)=1248, (6,4)=385 and (7,3)=168 communicated November 24, 22, 18, 12 and 1, 2005; (3,9)=576
communicated September 12, 2005; (3,10)=972, (3,11)=1536, communicated May 24,
2005; (4,7)=1200, communicated March 7, 2005; (7,3)=156, communicated August
22-28, 2004.
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 list of adjacencies. Click here.
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/Nov/24
Go back in time
and have a snapshot
of this table at different moments after 1995 thanks to the internet archive project.
