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 bounded above by the Moore bound; for and , only the Petersen graph, the Hoffman-Singleton graph, and possibly graphs (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.
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 .