MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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


For a given number of edges, the non directed graph which maximises the number of paths of length 2 is the quasi-star or the quasi-complete graph. Does anyone know :

1- what is the non directed graph which maximises the number of paths of length 3 2- same question for length 4 3- same question for length 3 + 4

If you have any hint, thank you very much.

share|cite|improve this question
Is the number of vertices also given? – Felix Goldberg Apr 10 '12 at 16:21
yes, sorry I forgot to mention. The number of vertices is also given. But if it helps, consider it can be as large as you wish and you don't need to connect them all. And by the way, I just noticed my mistake: I need the graphs which maximise the number of walks, not paths ! Sorry again – user20638 Apr 10 '12 at 18:58
Just a random note. Let $A$ be the adjacency matrix of your graph. The number of walks of length $k$ between vertices $v_i,v_j$ is given by the $(v_i,v_j)$ entry of $A^k$. Maybe this can help you somehow. – Jernej Apr 10 '12 at 20:40
yes, I know that. But I don't see how I can use it. – user20638 Apr 10 '12 at 20:43

Your Answer


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

Browse other questions tagged or ask your own question.