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.

$\endgroup$
  • $\begingroup$ What's hop-count? $\endgroup$ – Chris Godsil Jan 22 '13 at 12:52
1
$\begingroup$

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

| cite | improve this answer | |
$\endgroup$
  • $\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 '13 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.

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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