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 δ(x) is the number of vertices adjacent to x. The
degree of G is Δ=max_{x ∈ V}
δ(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 ∈ 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:
- 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.fr (Charles Delorme , LRI , who keeps the LaTeX table)
comellas@ma4.upc.edu ( Francesc Comellas , DMAT/combgraph , 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.
LARGEST KNOWN (Δ,D)-GRAPHS. August 2012.
References
- [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.edu ). 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.es). 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.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
- [Lo06] Eyal Loz ( eloz002@math.auckland.ac.nz ). 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.
- [Mo06] S.G. Molodtsov. Largest graphs of diameter 2 and maximum degree 6. LNCS 4123 (2006) 853-857.
- [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.be ) & 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.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
- [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:
- The (Degree, Diameter) problem for planar graphs. James Preen keeps
several tables for
the ( Δ,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)
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: August 27, 2012.
Go
back in time
and have a snapshot
of this table at different moments after 1995 thanks to the internet archive project.