0
$\begingroup$

I need to build a graph with number of vertexes N such that each vertex has degree at least k and the graph has the smallest diameter. I believe that this question should be well studied.

EDIT: yes complete graph is an answer, but not interesting. I am changing the question a little bit: each vertex has degree k.

  • 1
    This is almost a good question. The problem is that it appears you have put almost no effort into the question yourself. May I suggest including (a) necessary conditions on the existence of k-regular n-vertex graphs (b) resolving the 1-regular, 2-regular, (n-1)-regular and n-regular cases. Note, that PhD theses are written about the [degree-diameter problem](http://en.wikipedia.org/wiki/Degree_diameter_problem), and this is not far off -- it might be difficult to answer this question just for 3-regular (cubic) graphs.2012-10-25

1 Answers 1

1

The complete graph on $N$ vertices, $K_N$, will be hard to beat. If $k \gt N-1$ are you allowed multiple edges between a given pair of vertices? I hope so.

  • 0
    well, k < N - 12012-10-25