In graph theory, the degree diameter problem is the problem of finding the largest possible graph G (in terms of the size of its vertex set V) of diameter k 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 maybe a graph 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
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