Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Given $d$, $k$ and $n$ of a graph G where

$n$: the number of vertices in G,

$d$: the maximum vertex-degree in G,

$n$: the exact diameter of G,

what is maximum possible $|E|$ ? That is, what is the maximum number of edges in a graph that has the values $(d, k, n)$ as given ?

I am looking for references to this solution in literature.

Note that this is different than the degree-diameter problem -- the problem of finding maximum $|V|$ on given $(d,k)$ which is bounded by Moore's value.

Also note: I am aware of the "minimum", rather than "maximum $|E|$" version of this problem which has solutions for $k=2$ and $k=3$ in literature.

Thanks in advance.

share|cite|improve this question
I don't know of any references, sorry, but my gut feeling would be that the graph giving the maximal $|E|$ would be made up from a subgraph of complete graphs strung out in a path... If you take $t$ copies of $K_{d+1}$ and remove an edge from each, and then join the copies via the vertices which had the edge removed then you will get a graph with maximum degree $d$, diameter $2t-1$ and $td(d+1)/2-1$ edges. You can then delete some of the $td$ vertices until you have $n$ left. – jp26 Jan 13 '13 at 16:22
@jp26 Thank you for the input. However, I need the reference to cite. – ashley Jan 14 '13 at 8:27
Why do you believe such a reference exists? There are many unknown results about diameter... – jp26 Jan 14 '13 at 12:12
probably not worked. but it doesn't seem as hard as the lower bound which is solved in part. – ashley Jan 14 '13 at 12:25

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.