Given a number n of nodes, a diameter d (d>1) and a max-degree k. Let's assume d and k are chosen such that a graph with n nodes with the desired diameter and max-degree exists.


What is the minimum number of edges necessary to create a (connected) graph with n nodes, diameter d, and max-degree k? Is there a general construction rule to reach this graph?


Without the max-degree this question is trivially answered with n-1 by a star graph. How can we additionally deal with the max-degree? A better lower bound than n-1 would already be interesting.


Edit:d is meant to be an upper bound to the diameter.



Minimize edge number under diameter and max-degree constraint
I have found an answer to the question in a book by Béla Bollobás: Extremal Graph Theory. In chapter 4.1, he describes a lower bound:


Given maximal diameter $d$, maximal degree $k$, number of nodes $n$, number of edges $m$, the following inequality holds:


$m \geq \frac{n(n-1)(k-2)}{2((k-1)^d-1)}$


Sadly, I have not learned of any "construction rule" leading to a graph close to that bound.


