1

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.

flag
Is the number of vertices also given? – Felix Goldberg Apr 10 2012 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 – unknown (google) Apr 10 2012 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 2012 at 20:40
yes, I know that. But I don't see how I can use it. – unknown (google) Apr 10 2012 at 20:43

Your Answer

Get an OpenID
or

Browse other questions tagged or ask your own question.