In
graph theory
In mathematics, graph theory is the study of ''graphs'', which are mathematical structures used to model pairwise relations between objects. A graph in this context is made up of '' vertices'' (also called ''nodes'' or ''points'') which are conn ...
, the
degree diameter problem
In graph theory, the degree diameter problem is the problem of finding the largest possible graph (in terms of the size of its vertex set ) of diameter such that the largest degree of any of the vertices in is at most . The size of is bounde ...
is the problem of finding the largest possible
graph
Graph may refer to:
Mathematics
*Graph (discrete mathematics), a structure made of vertices and edges
**Graph theory, the study of such graphs and their properties
*Graph (topology), a topological space resembling a graph in the sense of discre ...
for a given maximum
degree and
diameter
In geometry, a diameter of a circle is any straight line segment that passes through the center of the circle and whose endpoints lie on the circle. It can also be defined as the longest chord of the circle. Both definitions are also valid fo ...
. The
Moore bound
In graph theory, a Moore graph is a regular graph whose girth (the shortest cycle length) is more than twice its diameter (the distance between the farthest two vertices). If the degree of such a graph is and its diameter is , its girth must ...
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
cycles 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 July 2022) in the undirected
degree diameter problem
In graph theory, the degree diameter problem is the problem of finding the largest possible graph (in terms of the size of its vertex set ) of diameter such that the largest degree of any of the vertices in is at most . The size of is bounde ...
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. Some general constructions are known for values of ''d'' and ''k'' outside the range shown in the table.
The following table is the key to the colors in the table presented above:
References
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
* {{citation
, last = Wegner
, first = Gerd
, title = Graphs with given diameter and a coloring problem
, year = 1977
, doi = 10.17877/DE290R-16496
, url = https://eldorado.tu-dortmund.de/bitstream/2003/34440/1/S0004501.pdf
External links
The Degree-Diameter Problem on CombinatoricsWiki.org
Eyal Loz'sdegree-diameter problem page (archived 2016.)
degree-diameter record graphs page (archived 2015.)
Guillermo Pineda-Villavicencio'sResearch page.
Graphs
Graphs