Degree diameter problem
For a finite simple undirected graph let denote its number of vertices, its maximum degree, and its diameter (the maximum, over all pairs of vertices, of the length of a shortest path joining them). For positive integers and set
and let
so that for all , and , , .
Determine for all integers . In particular, for every fixed integer ,
equivalently as with fixed; that is, writing , one has for every .
A graph with , and is a Moore graph; such a graph is necessarily -regular. There exists a Moore graph with and , i.e. a -regular graph on vertices of diameter .
References
- Wikipedia, Degree diameter problem, the article this problem comes from.
Source: Wikipedia
Progress summary
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
No solutions have been posted yet.