Degree diameter problem
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. 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 . See also
 Cage (graph theory)
 Table of the largest known graphs of a given diameter and maximal degree
 Table of vertex-symmetric degree diameter digraphs
 Maximum degree-and-diameter-bounded subgraph problem

References 
 

 

 

 

 

Computational problems in graph theory
Graph distance