Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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|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
add comment

Know someone who can answer? Share a link to this question via email, Google+, Twitter, or Facebook.

Your Answer

 
discard

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

Browse other questions tagged or ask your own question.