I need to build a graph with $N$ vertices such that each vertex has degree at least $k$ and the graph has the smallest diameter. What algorithm can I use?
migrated from cstheory.stackexchange.com Nov 15 '12 at 0:07
This question came from our site for theoretical computer scientists and researchers in related fields.
If $N > k$ then the complete graph $K_N$ is regular with degree $N-1 \geq k$, and has the smallest possible diameter $1$. If $N \leq k$ then there the degrees are bounded by $N-1 < k$, and so no such graph exists.