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
    Commented 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
    Commented 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$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .