The minimum possible degree of a graph of $n$ vertices, in which all pairs of nodes have a distance no more than $d$

Question

Here the degree of a graph is the maximum degree of all the vertices in the graph.
For example, when $n=4,d=2$, a cycle with 4 vertices is a solution, and a graph with 1 degree is not connected. So the answer is 2.
Is there an algorithm or a formula which can precisely give the answer of such problem when $n,d$ are fixed? If not, how to estimate the scale of the answer?

Answer 1

My answer is $$k=1+n^{1/{d}} $$ and the algorithm : take the graph randomly (and $k$ regular)

I turn the question into "What is the minimum diameter $d$ of a graph with $n$ vertices and with maximum degree k?". First notice that for from a root $x_0$ the maximum number of vertices at distance $r$ of the root is (trivially) bounded by the regular tree : and we have $$\text{#}[\text{dis}(x_0,x)\leq r] \leq k\sum_{i=0}^{r-1} (k-1)^i$$
This give rounghly $$n\leq k(k-1)^d $$ and so $$k\geq 1+n^{1/(d+2)}$$ Now the good news is that if you take randomly a $k$ regular graph this estimate is already not too bad. Indeed we have https://en.wikipedia.org/wiki/Random_regular_graph with high probability the diameter is smaller than $d$ if : $$(k-1)^{d-1}\geq (2+\epsilon)k n \log n $$ which gives $k-1\geq (n\log n)^{1/(d-2)}$ and we should not worry about the $\log n$. For an optimal minimiser, I would try the ramanudjan graph but it is more complicated http://www.mast.queensu.ca/~murty/ramanujan.pdf