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 
=
\max_{x \in V} Delta(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 \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 easily seen to be bounded by
This value is called the Moore bound, and 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.
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:
-
Geoff Exoo, yellow: 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, light 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].
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, responsible for the
LaTeX table)
comellas@mat.upc.es (
Francesc Comellas, DMAT
, who updates this WWW table).
This link is a gif
image of the same table.
LARGEST KNOWN ( ,D)-GRAPHS (June
1999)
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)-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.
-
Jean-Jacques Quisquater. Chordal rings. Communicated February 27, 1998)
-
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.
Related problems are:
-
The (Degree, Diameter) problem for planar graphs. Rob Pratt keeps several
Tables for the (
,D) problem for planar graphs
Eric Friedman
has also a table of Large
Regular Planar Graphs with Small Diameter.
-
The (
,D) problem for planar graphs proposed to kids, Megamath (LANL)
-
The ( ,D) vertex symmetric digraph
problem. We keep also a Table
of largest known (
,D) vertex symmetric digraphs.
-
The ( ,D,D, 1)- graph problem. The corresponding
Table
of largest known (
, D,D, 1)- graphs is also in this place.
Created: January, 1995; last changed: 2002/05/17.
