In graph theory

Graph theory

In mathematics and computer science, graph theory is the study of graphs, mathematical structures used to model pairwise relations between objects from a certain collection. A "graph" in this context refers to a collection of vertices or 'nodes' and a collection of edges that connect pairs of...

, the degree diameter problem

Degree diameter problem

In graph theory, the degree diameter problem is the problem of finding the largest possible graph G of diameter k such that the largest degree of any of the vertices in G is at most d...

 is the problem of finding the largest possible graph

Graph (mathematics)

In mathematics, a graph is an abstract representation of a set of objects where some pairs of the objects are connected by links. The interconnected objects are represented by mathematical abstractions called vertices, and the links that connect some pairs of vertices are called edges...

 for a given maximum degree

Degree (graph theory)

In graph theory, the degree of a vertex of a graph is the number of edges incident to the vertex, with loops counted twice. The degree of a vertex v is denoted \deg. The maximum degree of a graph G, denoted by Δ, and the minimum degree of a graph, denoted by δ, are the maximum and minimum degree...

 and diameter. The Moore bound sets limits on this, but for many years mathematicians in the field have been interested in a more precise answer. The table below gives current progress on this problem (excluding the case of degree 2, where the largest graphs are cycle

Cycle (graph theory)

In graph theory, the term cycle may refer to a closed path. If repeated vertices are allowed, it is more often called a closed walk. If the path is a simple path, with no repeated vertices or edges other than the starting and ending vertices, it may also be called a simple cycle, circuit, circle,...

s with an odd number of vertices).

Table of the orders of the largest known graphs for the undirected degree diameter problem

Below is the table of the vertex numbers for the best-known graphs (as of October 2008) in the undirected degree diameter problem

Degree diameter problem

In graph theory, the degree diameter problem is the problem of finding the largest possible graph G of diameter k such that the largest degree of any of the vertices in G is at most d...

 for graphs of degree at most 3 ≤ d ≤ 16 and diameter 2 ≤ k ≤ 10. Only a few of the graphs in this table (marked in bold) are known to be optimal (that is, largest possible). The remainder are merely the largest so far discovered, and thus finding a larger graph that is closer in order (in terms of the size of the vertex set) to the Moore bound is considered an open problem

Open problem

In science and mathematics, an open problem or an open question is a known problem that can be accurately stated, and has not yet been solved . Some questions remain unanswered for centuries before solutions are found...

. Some general constructions are known for values of d and k outside the range shown in the table.

\	2	3	4	5	6	7	8	9	10
3	10	20	38	70	132	196	336	600	1250
4	15	41	96	364	740	1 320	3 243	7 575	17 703
5	24	72	210	624	2 772	5 516	17 030	57 840	187 056
6	32	110	390	1404	7 917	19 383	76 461	307 845	1 253 615
7	50	168	672	2 756	11 988	52 768	249 660	1 223 050	6 007 230
8	57	253	1 100	5 060	39 672	131 137	734 820	4 243 100	24 897 161
9	74	585	1 550	8 200	75 893	279 616	1 686 600	12 123 288	65 866 350
10	91	650	2 286	13 140	134 690	583 083	4 293 452	27 997 191	201 038 922
11	104	715	3 200	19 500	156 864	1 001 268	7 442 328	72 933 102	600 380 000
12	133	786	4 680	29 470	359 772	1 999 500	15 924 326	158 158 875	1 506 252 500
13	162	851	6 560	40 260	531 440	3 322 080	29 927 790	249 155 760	3 077 200 700
14	183	916	8 200	57 837	816 294	6 200 460	55 913 932	600 123 780	7 041 746 081
15	186	1 215	11 712	76 518	1 417 248	8 599 986	90 001 236	1 171 998 164	10 012 349 898
16	198	1 600	14 640	132 496	1 771 560	14 882 658	140 559 416	2 025 125 476	12 951 451 931

The following table is the key to the colors in the table presented above:

Color	Details
*	The Petersen Petersen graph In the mathematical field of graph theory, the Petersen graph is an undirected graph with 10 vertices and 15 edges. It is a small graph that serves as a useful example and counterexample for many problems in graph theory. The Petersen graph is named for Julius Petersen, who in 1898 constructed it...  and Hoffman–Singleton graphs.
*	Optimal graphs which are not Moore graphs.
*	Graph found by James Allwright.
*	Graph found by G. Wegner.
*	Graphs found by Geoffrey Exoo.
*	Family of graphs found by Brendan D. McKay, Mirka Miller and Jozef Širáň. More details are available in a paper by the authors.
*	Graphs found by J. Gómez.
*	Graph found by Mitjana M. and Francesc Comellas. This graph was also found independently by Michael Sampels.
*	Graph found by Fiol, M.A. and Yebra, J.L.A.
*	Graph found by Francesc Comellas and J. Gómez.
*	Graphs found by G. Pineda-Villavicencio, J. Gómez, Mirka Miller and H. Pérez-Rosés. More details are available in a paper by the authors.
*	Graphs found by Eyal Loz. More details are available in a paper by Eyal Loz and Jozef Širáň.
*	Graphs found by Michael Sampels.
*	Graphs found by Michael J. Dinneen and Paul Hafner. More details are available in a paper by the authors.
*	Graph found by Marston Conder.

External links

• Degree Diameter online table.
• The Degree - Diameter Problem on CombinatoricsWiki.org.
• Eyal Loz's Degree-Diameter problem page.
• Geoffrey Exoo's Degree-Diameter record graphs page.
• Guillermo Pineda-Villavicencio's Research page.