0
$\begingroup$

Hi,

what is the minimal hop-count for a undirected (directed) graph (of size N) restricted to the number of edges per node (k)?

Clearly, it can be possible to build a graph with N and k in infinite ways, what I'm interested in is the maximum hops for an optimal graph.

For example, if I have a graph with N=N and k=N-1 then the solution I'm looking for is x=1. The hop-count for the best possible graph (all nodes are directly connected to any other) is one hop for each node.

I hope I make myself clear :), sorry if I don't.

The solution will look something like that:

x=N/k , with larger k and const. N, x needs to get larger, and vice versa.

Thanks a lot for the help. Please be nice if this is too unclear, easy, or redundant.

Improve this question
$\endgroup$
1
  • $\begingroup$ What's hop-count? $\endgroup$
    – Chris Godsil
    Jan 22, 2013 at 12:52

2 Answers 2

Reset to default
1
$\begingroup$

http://en.wikipedia.org/wiki/Degree_diameter_problem

Improve this answer
$\endgroup$
1
  • $\begingroup$ Hi, thanks for the help. I don't really got the answer I expected. It is not a random problem changing significantly with different graphs, is it? Shouldn't there be an answer in form of an equation? something like: x=N/k ? $\endgroup$
    – irvine
    Jan 22, 2013 at 17:29
0
$\begingroup$

Well what I was looking for is:

$d=\frac{ln(\frac{N(k-2)+2}{k})}{ln(k-1)}$

the Link helped, thx.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.