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:
Jul 30, 1997; (6,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: Jun 2003; (5,6), (8,6), (9,6), (10,6), (12,6),
(14,6) [15].
- J. Gómez Martí, M. Miller. Dark green: April 2005; (13,10),(15,7),(15,10) [17].
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. J. Gómez, M.A. Fiol and O. Serra, On large
(D, D) graphs,
Discrete Mathematics, 114 (1993), pp. 219—235.
C. Delorme, J. Gómez. Some new large compound graphs. European
Journal of Combinatorics, 23 (2002), pp. 539—547.
- 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. Networks 46 (2005), pp. 82—87.
- 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.
- J. Gómez Martí, M. Miller. Two new families of large compound graphs. Networks, to appear (2006).
- 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.
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/Dec/11
Go back in time
and have a snapshot
of this table at different moments after 1995 thanks to the internet archive project.
