# Resticted number of edges, optimal connected graph

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.

-
What's hop-count? –  Chris Godsil Jan 22 '13 at 12:52

-
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 ? –  irvine Jan 22 '13 at 17:29

Well what I was looking for is:

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