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 conne ...
, the degree diameter problem 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 ...
(in terms of the size of its
vertex
Vertex, vertices or vertexes may refer to:
Science and technology Mathematics and computer science
*Vertex (geometry), a point where two or more curves, lines, or edges meet
* Vertex (computer graphics), a data structure that describes the positio ...
set ) of
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 for ...
such that the largest
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
...
of any of the vertices in is at most . The size of is bounded above by 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 ...
; for and only the
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 n ...
, the
Hoffman-Singleton graph, and possibly one more graph (not yet proven to exist) of diameter and degree attain the Moore bound. In general, the largest degree-diameter graphs are much smaller in size than the Moore bound.
Formula
Let
be the maximum possible number of vertices for a graph with degree at most ''d'' and diameter ''k''. Then
, where
is 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 ...
:
:
This bound is attained for very few graphs, thus the study moves to how close there exist graphs to the Moore bound.
For asymptotic behaviour note that
.
Define the parameter
. It is conjectured that
for all ''k''. It is known that
and that
.
See also
*
Cage (graph theory)
In the mathematical area of graph theory, a cage is a regular graph that has as few vertices as possible for its girth.
Formally, an is defined to be a graph in which each vertex has exactly neighbors, and in which the shortest cycle has len ...
*
Table of degree diameter graphs
*
Table of vertex-symmetric degree diameter digraphs
*
Maximum degree-and-diameter-bounded subgraph problem
References
*
*
*
*
* {{citation
, title = CombinatoricsWiki - The Degree/Diameter Problem
, url = http://combinatoricswiki.org/wiki/The_Degree/Diameter_Problem
Computational problems in graph theory
Graph distance