MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top


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.

share|cite|improve this question
What's hop-count? – Chris Godsil Jan 22 '13 at 12:52

share|cite|improve this answer
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:


the Link helped, thx.

share|cite|improve this answer

Your Answer


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

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