In
graph theory, the
degree diameter problem is the problem of finding the largest possible
graph for a given maximum
degree
Degree may refer to:
As a unit of measurement
* Degree (angle), a unit of angle measurement
** Degree of geographical latitude
** Degree of geographical longitude
* Degree symbol (°), a notation used in science, engineering, and mathematics
...
and
diameter. 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
cycle
Cycle, cycles, or cyclic may refer to:
Anthropology and social sciences
* Cyclic history, a theory of history
* Cyclical theory, a theory of American political history associated with Arthur Schlesinger, Sr.
* Social cycle, various cycles in soc ...
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 July 2022) in the undirected
degree diameter problem 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 In science and mathematics, an open problem or an open question is a known problem which can be accurately stated, and which is assumed to have an objective and verifiable solution, but which has not yet been solved (i.e., no solution for it is know ...
. 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
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 ...