# graphs with maximal number of paths of given length

Hi,

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.

-
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