Finding the largest graph of given diameter and degree
In
graph theory, the degree diameter problem is the problem of finding the largest possible
graphG (in terms of the size of its
vertex set V) of
diameterk such that the largest
degree of any of the vertices in G is at most d. The size of G is bounded above by the
Moore bound; for 1 < k and 2 < d only the
Petersen graph, the
Hoffman-Singleton graph, and possibly graphs (not yet proven to exist) of diameter k = 2 and degree d = 57 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:
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 .